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

Question

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

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%肯定,但我认为无堆栈转换只适用于原始递归函数.我看不出像Ackermann函数这样的东西可以在没有某种堆栈的情况下计算出来.)

无论如何,对于实践中的大多数情况(以及课堂中的所有情况),都可以找到一种方法.在这里我们可以使用反击技巧:

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

更新: 转换这样的简单函数最简单实用的方法是运行它,在每次迭代后写下输出,然后完全忘记递归,忘记原始代码,单独查看输出并问自己:这是什么代码在做什么？然后尝试编写产生相同输出的迭代代码.这项技术在uni上很有用.但它并不总是在现实生活中起作用.:)