如何最好地将递归函数转换为迭代函数? [英] How do you best convert a recursive function to an iterative one?

问题描述

这个问题是基于我在 compsci 课上的一个测试.特别是，我正在努力转换此功能:

This question is based on a test I had in a compsci class. In particular, I'm struggling to convert this function:

public static void foo(int number)  {
    if (number > 0) {
        foo(number / 2);
        System.out.print(number % 2);
    }
}

我需要将此函数转换为非递归函数，但我正在努力解决它，因为 System.out.print(number % 2) 发生在递归调用之后.

I need to convert this function to be non-recursive, but I'm struggling with it because the System.out.print(number % 2) occurs after the recursive call.

推荐答案

当然，您始终可以模拟堆栈，但在很多情况下，您可以将其转换为完全无堆栈的解决方案.(我不是 100% 确定，但我认为无堆栈转换仅适用于 原始递归函数. 我看不出像 Ackermann 函数 之类的东西可以在没有某种堆栈的情况下进行计算.)

You can always simulate the stack of course but in a lot of cases you can convert it to a completely stackless solution. (I'm not 100% sure but I think the stack-free conversion is only possible for primitive recursive functions. I can see no way something like the Ackermann function can be computed without some sort of stack.)

无论如何，对于实践中的大多数情况(以及课堂中的所有情况)，都有可能找到方法.这里我们可以使用计数器技巧:

Anyway, for most cases in practice (and all cases in the class room) it is possible to find a way. Here we can use the counter trick:

public static void foo(int number)  {
    for ( int divisor = 1; divisor <= number; divisor *= 2) {
      System.out.print( (number / divisor) % 2 );
    }
}

更新:像这样转换简单函数的最简单实用的方法是运行它，写下每次迭代后的输出，然后完全忘记递归，忘记原始代码，单独看输出并问自己:这是什么代码在做什么?然后尝试编写产生相同输出的迭代代码.这种技术在大学里对我很有帮助.但它在现实生活中并不总是有效.:)

这篇关于如何最好地将递归函数转换为迭代函数?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！