如何使用堆栈模拟递归？

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

说明:每次从堆栈中获取项目时,都需要检查是否需要扩展它.如果是这样,在堆栈上推送适当的参数,如果没有,让它与之前的结果合并.在fibonacci的情况下,一旦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

Answer 2

您的特定示例是尾递归的，因此使用正确优化的编译器，它根本不应该消耗任何堆栈深度，因为它相当于一个简单的循环。需要明确的是：这个示例根本不需要堆栈。