java - 如何最好地将递归函数转换为迭代函数？

Question

此问题基于我在 compsci 类(class)中进行的测试。特别是，我正在努力转换此功能:

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

我需要将此函数转换为非递归函数，但我正在为此苦苦挣扎，因为 System.out.print(number % 2) 发生在递归调用之后。

Answer 1

当然，您始终可以模拟堆栈，但在很多情况下，您可以将其转换为完全无堆栈的解决方案。 (我不是 100% 确定，但我认为无堆栈转换仅适用于 primitive recursive functions 。我看不出没有某种堆栈可以计算类似 Ackermann function 的东西。)

无论如何，对于实践中的大多数情况(以及类里面的所有情况)，都可以找到一种方法。在这里我们可以使用计数器技巧:

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

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