从递归到迭代的方法-Java 学习之路

289

在我多年的编程中，我已经使用递归来解决简单的问题，但我完全清楚有时候你需要迭代来解决内存/速度问题 .

所以，在过去的某个时候，我去尝试找出是否存在任何“模式”或文本书方式将常见的递归方法转换为迭代而没有发现任何东西 . 或者至少我记不住任何事都会有所帮助 .

是否有一般规则？
有"pattern"吗？

19 回答

要查找的一种模式是函数末尾的递归调用（所谓的尾递归） . 这可以很容易地替换一段时间 . 例如，函数foo：

void foo(Node* node)
{
    if(node == NULL)
       return;
    // Do something with node...
    foo(node->left);
    foo(node->right);
}

最后打电话给foo . 这可以替换为：

void foo(Node* node)
{
    while(node != NULL)
    {
        // Do something with node...
        foo(node->left);
        node = node->right;
     }
}

这消除了第二次递归调用 .

回复于 2024-04-20T01:59:06+08:00

42
通常，我通过将通常传递给递归函数的参数推送到堆栈上，通过迭代算法替换递归算法 . 实际上，您正在用自己的程序替换程序堆栈 .
```
Stack<Object> stack;
stack.push(first_object);
while( !stack.isEmpty() ) {
   // Do something
   my_object = stack.pop();

  // Push other objects on the stack.

}
```
注意：如果您内部有多个递归调用，并且您希望保留调用的顺序，则必须以相反的顺序将它们添加到堆栈中：
```
foo(first);
foo(second);
```
必须被替换
```
stack.push(second);
stack.push(first);
```
编辑：文章Stacks and Recursion Elimination（或Article Backup link）详细介绍了这个主题 .
回复于 2024-04-20T01:59:06+08:00

实际上，最常见的方法是保留自己的堆栈 . 这是C中的递归quicksort函数：

void quicksort(int* array, int left, int right)
{
    if(left >= right)
        return;

    int index = partition(array, left, right);
    quicksort(array, left, index - 1);
    quicksort(array, index + 1, right);
}

以下是我们如何通过保持自己的堆栈来迭代：

void quicksort(int *array, int left, int right)
{
    int stack[1024];
    int i=0;

    stack[i++] = left;
    stack[i++] = right;

    while (i > 0)
    {
        right = stack[--i];
        left = stack[--i];

        if (left >= right)
             continue;

        int index = partition(array, left, right);
        stack[i++] = left;
        stack[i++] = index - 1;
        stack[i++] = index + 1;
        stack[i++] = right;
    }
}

显然，这个例子没有检查堆栈边界......实际上你可以根据给定左右值的最坏情况来调整堆栈的大小 . 但是你明白了 .

回复于 2024-04-20T01:59:06+08:00

似乎没有人解决递归函数在正文中多次调用自身的问题，并处理递归到递归中的特定点（即不是原始递归） . 据说every recursion can be turned into iteration，所以看来这应该是可能的 .

我刚刚想出了一个如何做到这一点的C＃示例 . 假设您具有以下递归函数，其作用类似于后序遍历，并且AbcTreeNode是具有指针a，b，c的3-ary树 .

public static void AbcRecursiveTraversal(this AbcTreeNode x, List<int> list) {
        if (x != null) {
            AbcRecursiveTraversal(x.a, list);
            AbcRecursiveTraversal(x.b, list);
            AbcRecursiveTraversal(x.c, list);
            list.Add(x.key);//finally visit root
        }
}

迭代解决方案：

int? address = null;
        AbcTreeNode x = null;
        x = root;
        address = A;
        stack.Push(x);
        stack.Push(null)    

        while (stack.Count > 0) {
            bool @return = x == null;

            if (@return == false) {

                switch (address) {
                    case A://   
                        stack.Push(x);
                        stack.Push(B);
                        x = x.a;
                        address = A;
                        break;
                    case B:
                        stack.Push(x);
                        stack.Push(C);
                        x = x.b;
                        address = A;
                        break;
                    case C:
                        stack.Push(x);
                        stack.Push(null);
                        x = x.c;
                        address = A;
                        break;
                    case null:
                        list_iterative.Add(x.key);
                        @return = true;
                        break;
                }

            }


            if (@return == true) {
                address = (int?)stack.Pop();
                x = (AbcTreeNode)stack.Pop();
            }


        }

回复于 2024-04-20T01:59:06+08:00

1

努力使你的递归调用Tail Recursion（最后一个语句是递归调用的递归） . 一旦你有了，将其转换为迭代通常很容易 .

回复于 2024-04-20T01:59:06+08:00
2
嗯，通常，通过简单地使用存储变量，可以将递归模仿为迭代 . 请注意，递归和迭代通常是等效的;一个人几乎总能转换成另一个人 . 尾递归函数很容易转换为迭代函数 . 只需将累加器变量设为局部变量，然后迭代而不是递归 . 这是C中的一个例子（C不是因为使用了默认参数）：
```
// tail-recursive
int factorial (int n, int acc = 1)
{
  if (n == 1)
    return acc;
  else
    return factorial(n - 1, acc * n);
}

// iterative
int factorial (int n)
{
  int acc = 1;
  for (; n > 1; --n)
    acc *= n;
  return acc;
}
```
知道我，我可能在代码中犯了一个错误，但想法就在那里 .
回复于 2024-04-20T01:59:06+08:00
6

即使使用堆栈也不会将递归算法转换为迭代算法 . 正常递归是基于函数的递归，如果我们使用堆栈，那么它将成为基于堆栈的递归 . 但它仍然是递归 .

对于递归算法，空间复杂度为O（N），时间复杂度为O（N） . 对于迭代算法，空间复杂度为O（1），时间复杂度为O（N） .

但是如果我们使用堆栈的东西在复杂性方面保持不变 . 我认为只有尾递归可以转换为迭代 .

回复于 2024-04-20T01:59:06+08:00

stacks and recursion elimination文章捕获了在堆上外部化堆栈帧的想法，但没有提供 straightforward and repeatable 转换方式 . 下面是一个 .

在转换为迭代代码时，必须意识到递归调用可能来自任意深度的代码块 . 它不仅仅是参数，还包括返回到仍然要执行的逻辑的点和参与后续条件的变量的状态，这很重要 . 下面是一种非常简单的方法，可以转换为迭代代码，只需更改 .

考虑这个递归代码：

struct tnode
{
    tnode(int n) : data(n), left(0), right(0) {}
    tnode *left, *right;
    int data;
};

void insertnode_recur(tnode *node, int num)
{
    if(node->data <= num)
    {
        if(node->right == NULL)
            node->right = new tnode(num);
        else
            insertnode(node->right, num);
    }
    else
    {
        if(node->left == NULL)
            node->left = new tnode(num);
        else
            insertnode(node->left, num);
    }    
}

迭代代码：

// Identify the stack variables that need to be preserved across stack 
// invocations, that is, across iterations and wrap them in an object
struct stackitem 
{ 
    stackitem(tnode *t, int n) : node(t), num(n), ra(0) {}
    tnode *node; int num;
    int ra; //to point of return
};

void insertnode_iter(tnode *node, int num) 
{
    vector<stackitem> v;
    //pushing a stackitem is equivalent to making a recursive call.
    v.push_back(stackitem(node, num));

    while(v.size()) 
    {
        // taking a modifiable reference to the stack item makes prepending 
        // 'si.' to auto variables in recursive logic suffice
        // e.g., instead of num, replace with si.num.
        stackitem &si = v.back(); 
        switch(si.ra)
        {
        // this jump simulates resuming execution after return from recursive 
        // call 
            case 1: goto ra1;
            case 2: goto ra2;
            default: break;
        } 

        if(si.node->data <= si.num)
        {
            if(si.node->right == NULL)
                si.node->right = new tnode(si.num);
            else
            {
                // replace a recursive call with below statements
                // (a) save return point, 
                // (b) push stack item with new stackitem, 
                // (c) continue statement to make loop pick up and start 
                //    processing new stack item, 
                // (d) a return point label
                // (e) optional semi-colon, if resume point is an end 
                // of a block.

                si.ra=1;
                v.push_back(stackitem(si.node->right, si.num));
                continue; 
ra1:            ;         
            }
        }
        else
        {
            if(si.node->left == NULL)
                si.node->left = new tnode(si.num);
            else
            {
                si.ra=2;                
                v.push_back(stackitem(si.node->left, si.num));
                continue;
ra2:            ;
            }
        }

        v.pop_back();
    }
}

注意代码的结构如何仍然适用于递归逻辑，并且修改是最小的，从而导致更少的错误 . 为了比较，我用 - 和标记了变化 . 除了v.push_back之外，大多数新插入的块对于任何转换的迭代逻辑都是通用的

void insertnode_iter(tnode *node, int num) 
{

+++++++++++++++++++++++++

vector<stackitem> v;
    v.push_back(stackitem(node, num));

    while(v.size())
    {
        stackitem &si = v.back(); 
        switch(si.ra)
        {
            case 1: goto ra1;
            case 2: goto ra2;
            default: break;
        }

------------------------

if(si.node->data <= si.num)
        {
            if(si.node->right == NULL)
                si.node->right = new tnode(si.num);
            else
            {

+++++++++++++++++++++++++

si.ra=1;
                v.push_back(stackitem(si.node->right, si.num));
                continue; 
ra1:            ;

-------------------------

}
        }
        else
        {
            if(si.node->left == NULL)
                si.node->left = new tnode(si.num);
            else
            {

+++++++++++++++++++++++++

si.ra=2;                
                v.push_back(stackitem(si.node->left, si.num));
                continue;
ra2:            ;

-------------------------

}
        }

+++++++++++++++++++++++++

v.pop_back();
    }

-------------------------

回复于 2024-04-20T01:59:06+08:00

277

搜索谷歌“继续传递风格” . 转换为尾递归样式有一个通用的过程;还有一个将尾递归函数转换为循环的通用过程 .

回复于 2024-04-20T01:59:06+08:00

只是消磨时间......一个递归函数

void foo(Node* node)
{
    if(node == NULL)
       return;
    // Do something with node...
    foo(node->left);
    foo(node->right);
}

可以转换为

void foo(Node* node)
{
    if(node == NULL)
       return;

    // Do something with node...

    stack.push(node->right);
    stack.push(node->left);

    while(!stack.empty()) {
         node1 = stack.pop();
         if(node1 == NULL)
            continue;
         // Do something with node1...
         stack.push(node1->right);             
         stack.push(node1->left);
    }

}

回复于 2024-04-20T01:59:06+08:00

通常，避免堆栈溢出的技术是递归函数，称为trampoline技术，Java开发人员广泛采用 .

但是，对于C＃，有一个小帮助方法here可以将递归函数转换为迭代函数，而无需更改逻辑或使代码易于理解 . C＃是一种非常好的语言，可以用它来实现惊人的东西 .

它的工作原理通过辅助方法包装方法的一部分 . 例如以下递归函数：

int Sum(int index, int[] array)
{
 //This is the termination condition
 if (int >= array.Length)
 //This is the returning value when termination condition is true
 return 0;

//This is the recursive call
 var sumofrest = Sum(index+1, array);

//This is the work to do with the current item and the
 //result of recursive call
 return array[index]+sumofrest;
}

变成：

int Sum(int[] ar)
{
 return RecursionHelper<int>.CreateSingular(i => i >= ar.Length, i => 0)
 .RecursiveCall((i, rv) => i + 1)
 .Do((i, rv) => ar[i] + rv)
 .Execute(0);
}

回复于 2024-04-20T01:59:06+08:00

12

我只是赞成建议使用我认为是正确的解决方案并具有普遍适用性的显式堆栈的答案 .

我的意思是你可以用它来转换迭代函数中的任何递归函数 . 只需检查在递归调用中保存哪些值，这些值必须是递归函数的本地值，并用一个循环替换调用，在那里将它们推送到堆栈上 . 当堆栈为空时，递归函数将被终止 .

我无法抗拒地说每个递归函数相当于不同数据类型的迭代函数的证据，这是我对大学时代最亲密的记忆之一 . 那是真正让我理解计算机编程是什么的课程（和教授） .

回复于 2024-04-20T01:59:06+08:00

作为此副本的副本而关闭的question具有非常具体的数据结构：

enter image description here

该节点具有以下结构：

typedef struct {
    int32_t type;
    int32_t valueint;
    double  valuedouble;
    struct  cNODE *next;
    struct  cNODE *prev;
    struct  cNODE *child;
} cNODE;

递归删除函数看起来像：

void cNODE_Delete(cNODE *c) {
    cNODE*next;
    while (c) {
        next=c->next;
        if (c->child) { 
          cNODE_Delete(c->child)
        }
        free(c);
        c=next;
    }
}

通常，并不总是可以避免堆栈的递归函数多次调用（或甚至一次） . 但是，对于这种特定的结构，它是可能的 . 我们的想法是将所有节点展平为一个列表 . 这是通过将当前节点的 child 放在顶行列表的末尾来实现的 .

void cNODE_Delete (cNODE *c) {
    cNODE *tmp, *last = c;
    while (c) {
        while (last->next) {
            last = last->next;   /* find last */
        }
        if ((tmp = c->child)) {
            c->child = NULL;     /* append child to last */
            last->next = tmp;
            tmp->prev = last;
        }
        tmp = c->next;           /* remove current */
        free(c);
        c = tmp;
    }
}

该技术可以应用于任何数据链接结构，该结构可以通过确定性拓扑排序减少为DAG . 重新排列当前节点子节点，以便最后一个子节点采用所有其他子节点 . 然后可以删除当前节点，然后遍历可以迭代到剩余的子节点 .

回复于 2024-04-20T01:59:06+08:00

0

递归只不过是从另一个函数调用一个函数的过程，只有这个过程是通过自己调用一个函数来完成的 . 正如我们所知，当一个函数调用另一个函数时，第一个函数保存其状态（其变量），然后将控件传递给被调用的函数 . 调用函数可以通过使用相同名称的变量来调用ex fun1（a）可以调用fun2（a） . 当我们做递归调用时，没有任何新的事情发生 . 一个函数通过在名称变量中传递相同类型和类似的函数来调用自身（但显然存储在变量中的值是不同的，只有名称保持不变 . ） . 但在每次调用之前，函数都会保存其状态，并且此保存过程将继续 . 拯救已经完成了堆叠 .

现在堆栈进入播放状态 .

因此，如果您编写一个迭代程序并每次将状态保存在堆栈上，然后在需要时从堆栈中弹出值，您已成功将递归程序转换为迭代程序！

证明简单而有分析性 .

在递归中，计算机维护堆栈，在迭代版本中，您必须手动维护堆栈 .

考虑一下，只需将深度优先搜索（在图表上）递归程序转换为dfs迭代程序 .

祝一切顺利！

回复于 2024-04-20T01:59:06+08:00

思考实际需要堆栈的事情：

如果我们将递归模式视为：

if(task can be done directly) {
    return result of doing task directly
} else {
    split task into two or more parts
    solve for each part (possibly by recursing)
    return result constructed by combining these solutions
}

例如，经典的河内塔

if(the number of discs to move is 1) {
    just move it
} else {
    move n-1 discs to the spare peg
    move the remaining disc to the target peg
    move n-1 discs from the spare peg to the target peg, using the current peg as a spare
}

这可以转换为在显式堆栈上工作的循环，通过将其重新设置为：

place seed task on stack
while stack is not empty 
   take a task off the stack
   if(task can be done directly) {
      Do it
   } else {
      Split task into two or more parts
      Place task to consolidate results on stack
      Place each task on stack
   }
}

对于河内塔，这变为：

stack.push(new Task(size, from, to, spare));
while(! stack.isEmpty()) {
    task = stack.pop();
    if(task.size() = 1) {
        just move it
    } else {
        stack.push(new Task(task.size() -1, task.spare(), task,to(), task,from()));
        stack.push(new Task(1, task.from(), task.to(), task.spare()));
        stack.push(new Task(task.size() -1, task.from(), task.spare(), task.to()));
    }
}

关于如何定义堆栈，这里有相当大的灵活性 . 您可以使堆栈成为复杂事物的 Command 对象列表 . 或者你可以向相反的方向前进并使其成为更简单类型的列表（例如"task"可能是 int 堆栈上的4个元素，而不是 Task 堆栈上的一个元素） .

所有这些意味着堆栈的内存在堆中而不是在Java执行堆栈中，但这可能是有用的，因为您可以更好地控制它 .

回复于 2024-04-20T01:59:06+08:00

28
粗略描述系统如何获取任何递归函数并使用堆栈执行它：

这旨在显示没有细节的想法 . 考虑这个打印图形节点的函数：
```
function show(node)
0. if isleaf(node):
1.  print node.name
2. else:
3.  show(node.left)
4.  show(node)
5.  show(node.right)
```
例如图：A-> B A-> C表示（A）将打印B，A，C

函数调用意味着保存本地状态和延续点，以便您可以返回，然后跳转要调用的函数 .

例如，假设show（A）开始运行 . 第3行的函数调用 . 显示（B）表示 - 向堆栈添加项目意味着“您需要在第2行继续使用局部变量状态节点= A” - 转到第0行，其中node = B.

要执行代码，系统将运行指令 . 遇到函数调用时，系统会推送它需要的信息回到原来的位置，运行功能代码，当功能完成后，弹出有关继续运行的信息 .
回复于 2024-04-20T01:59:06+08:00
5
这个link提供了一些解释，并提出了让"location"能够到达几个递归调用之间的确切位置的想法：

但是，所有这些示例都描述了递归调用是固定次数的情况 . 当你有类似的东西时，事情变得棘手：
```
function rec(...) {
  for/while loop {
    var x = rec(...)
    // make a side effect involving return value x
  }
}
```
回复于 2024-04-20T01:59:06+08:00
1

通过使用连接多个迭代器供应器的lazy迭代器（lambda表达式返回迭代器），有一种将递归遍历转换为迭代器的一般方法 . 看我的Converting Recursive Traversal to Iterator .

回复于 2024-04-20T01:59:06+08:00

另一个使用堆栈将递归函数转换为迭代函数的简单而完整的示例 .

#include <iostream>
#include <stack>
using namespace std;

int GCD(int a, int b) { return b == 0 ? a : GCD(b, a % b); }

struct Par
{
    int a, b;
    Par() : Par(0, 0) {}
    Par(int _a, int _b) : a(_a), b(_b) {}
};

int GCDIter(int a, int b)
{
    stack<Par> rcstack;

    if (b == 0)
        return a;
    rcstack.push(Par(b, a % b));

    Par p;
    while (!rcstack.empty()) 
    {
        p = rcstack.top();
        rcstack.pop();
        if (p.b == 0)
            continue;
        rcstack.push(Par(p.b, p.a % p.b));
    }

    return p.a;
}

int main()
{
    //cout << GCD(24, 36) << endl;
    cout << GCDIter(81, 36) << endl;

    cin.get();
    return 0;
}

回复于 2024-04-20T01:59:06+08:00

从递归到迭代的方法

19 回答

相关问题