language-agnostic - 如何用堆栈模拟递归？

Question

听说任何递归算法都可以用栈来表示。最近，我一直在一个可用调用堆栈非常小的环境中编写程序。

我需要做一些深度递归，所以我想知道如何重新设计任何递归算法以使用显式堆栈。

例如，假设我有这样一个递归函数

function f(n, i) {
  if n <= i return n
  if n % i = 0 return f(n / i, i)
  return f(n, i + 1)
}

我怎么能用堆栈来写呢？是否有一个简单的过程可以将任何递归函数转换为基于堆栈的函数？

Answer 1

如果您了解函数调用如何影响进程堆栈，您就可以了解如何自己做。

当你调用一个函数时，一些数据被写入堆栈，包括参数。该函数读取这些参数，对它们执行任何操作并将结果放在堆栈上。你可以做同样的事情。您的示例特别不需要堆栈，因此如果我将其转换为使用堆栈的示例，它可能看起来有点傻，所以我将为您提供斐波那契示例:

fib(n)
    if n < 2 return n
    return fib(n-1) + fib(n-2)

function fib(n, i)
    stack.empty()
    stack.push(<is_arg, n>)
    while (!stack.size() > 2 || stack.top().is_arg)
        <isarg, argn> = stack.pop()
        if (isarg)
            if (argn < 2)
                stack.push(<is_result, argn>)
            else
                stack.push(<is_arg, argn-1>)
                stack.push(<is_arg, argn-2>)
        else
            <isarg_prev, argn_prev> = stack.pop()
            if (isarg_prev)
                stack.push(<is_result, argn>)
                stack.push(<is_arg, argn_prev>)
            else
                stack.push(<is_result, argn+argn_prev>)
     return stack.top().argn

解释:每次从栈中取出一个元素，都需要检查是否需要展开。如果是，将适当的参数压入堆栈，如果不是，让它与之前的结果合并。在斐波那契的情况下，一旦 fib(n-2) 被计算(并且在栈顶可用)，n-1 被检索(一个在栈顶之后), fib(n-2) 的结果被推到它下面，然后 fib(n-1) 被扩展和计算。如果栈顶的两个元素都是结果，当然，你只需将它们相加并入栈即可。

如果您想查看您自己的函数的外观，请看这里:

function f(n, i)
    stack.empty()
    stack.push(n)
    stack.push(i)
    while (!stack.is_empty())
        argi = stack.pop()
        argn = stack.pop()
        if argn <= argi
            result = argn
        else if n % i = 0
            stack.push(n / i)
            stack.push(i)
        else
            stack.push(n)
            stack.push(i + 1)
    return result