如何使用堆栈模拟递归? [英] How can you emulate recursion with a stack?

问题描述

我听说，任何递归算法都可以始终通过使用堆栈来表示.最近，我一直在一个可用调用堆栈大小非常小的环境中开发程序.

I've heard that any recursive algorithm can always be expressed by using a stack. Recently, I've been working on programs in an environment with a prohibitively small available call stack size.

我需要做一些深层递归，所以我想知道如何重做任何递归算法以使用显式堆栈.

I need to do some deep recursion, so I was wondering how you could rework any recursive algorithm to use an explicit stack.

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

For example, let's suppose I have a recursive function like this

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

我该如何用堆栈写呢?我可以遵循一个简单的过程将任何递归函数转换为基于堆栈的函数吗?

how could I write it with a stack instead? Is there a simple process I can follow to convert any recursive function into a stack-based one?

推荐答案

如果您了解函数调用如何影响流程堆栈，则可以自己了解如何实现.

If you understand how a function call affects the process stack, you can understand how to do it yourself.

调用函数时，某些数据(包括参数)被写入堆栈中.该函数读取这些参数，对其进行任何处理，然后将结果放置在堆栈中.您可以做完全相同的事情.特别是您的示例不需要堆栈，因此，如果我将其转换为使用堆栈的堆栈，则看起来可能有些愚蠢，因此，我将为您提供斐波那契示例:

When you call a function, some data are written on the stack including the arguments. The function reads these arguments, does whatever with them and places the result on the stack. You can do the exact same thing. Your example in particular doesn't need a stack so if I convert that to one that uses stack it may look a bit silly, so I'm going to give you the fibonacci example:

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)被扩展和计算.当然，如果堆栈的前两个元素都是结果，则只需将它们添加并压入堆栈.

Explanation: every time you take an item from the stack, you need to check whether it needs to be expanded or not. If so, push appropriate arguments on the stack, if not, let it merge with previous results. In the case of fibonacci, once fib(n-2) is computed (and is available at top of stack), n-1 is retrieved (one after top of stack), result of fib(n-2) is pushed under it, and then fib(n-1) is expanded and computed. If the top two elements of the stack were both results, of course, you just add them and push to stack.

如果您想查看自己的函数的外观，则为:

If you'd like to see how your own function would look like, here it is:

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

这篇关于如何使用堆栈模拟递归?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！