recursion - 递归算法 - 递归迭代回溯




从递归到迭代的方法 (12)

为了解决简单的问题,我在编程上花了很多年的时间用了很多递归,但是我完全意识到有时候由于内存/速度的问题需要迭代。

所以,在很久以前的某个时候,我去试图找出是否有任何“模式”或文本书的方式来改变一个共同的递归方法迭代,什么都没有发现。 或者至少没有什么,我能记得它会帮助。

  • 有一般规则吗?
  • 有没有“模式”?

努力使你的递归调用尾递归 (递归最后一个语句是递归调用)。 一旦你有了,把它转换成迭代通常很容易。


搜索谷歌的“继续传递风格”。 有一个转换为尾递归风格的一般程序; 还有一个把尾递归函数转换成循环的一般过程。


要查找的一种模式是函数末尾的递归调用(所谓的尾递归)。 这可以很容易地被替换一段时间。 例如,函数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;
     }
}

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


我刚刚提出了一个答案,建议使用一个明确的堆栈,我认为这是正确的解决方案,具有普遍的适用性。

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

我无法抗拒地说,每一个递归函数都等价于一个不同数据类型的迭代函数,这是我大学时代的一个最珍贵的记忆。 这是真正让我明白计算机编程是关于什么的课程(和教授)。


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

对于递归算法,空间复杂度为O(N),时间复杂度为O(N)。 对于迭代算法,空间复杂度为O(1),时间复杂度为O(N)。

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


那么,一般来说,递归可以通过简单地使用一个存储变量来模仿迭代。 请注意,递归和迭代通常是等价的; 几乎总是可以转换为另一个。 尾递归函数很容易转换为迭代函数。 只要使累加器变量为本地变量,并迭代而不是递归。 这是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;
}

了解我,我可能在代码中犯了一个错误,但是这个想法就在那里。


通常避免堆栈溢出的技术是递归函数,被称为蹦床技术,被Java开发人员广泛采用。

但是,对于C#来说,这里有一个小的帮助器方法可以将递归函数转换为迭代,而不需要更改逻辑或使代码不可理解。 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);
}

系统如何使用递归函数并使用堆栈执行它的粗略描述:

这旨在表明没有细节的想法。 考虑这个函数将打印出一个图的节点:

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)开始运行。 show(B)表示 - 将项目添加到堆栈,意思是“您将需要在局部变量状态node = A的第2行继续” - 转到line 0,node = B。

为了执行代码,系统运行指令。 遇到函数调用时,系统会将需要返回的信息推回到原来的位置,运行函数代码,函数完成后会弹出关于需要继续的位置的信息。


这个链接提供了一些解释,并提出了保持“位置”能够到达几个递归调用之间的确切位置的想法:

但是,所有这些例子都描述了递归调用被固定的时间量的情况。 事情变得棘手,当你有这样的事情:

function rec(...) {
  for/while loop {
    var x = rec(...)
    // make a side effect involving return value x
  }
}

通常,我通过迭代算法将通常传递给递归函数的参数推送到堆栈上来替换递归算法。 事实上,你正在用自己的方法来替换程序堆栈。

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);

编辑:文章堆栈和递归消除 (或文章备份链接 )进入这个问题的更多细节。


作为这个问题的一个重复的问题有一个非常具体的数据结构:

该节点具有以下结构:

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的数据链接结构。 当前节点的孩子被重新排列,以便最后一个孩子能够接纳所有其他的孩子。 然后,当前节点可以被删除,遍历可以迭代到剩下的孩子。


思考事实上需要一个堆栈:

如果我们把递归模式看作:

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对象。 或者你可以走相反的方向,使它成为一个简单类型的列表(例如,一个“任务”可能是一个int堆栈中的4个元素,而不是Task栈中的一个元素)。

所有这一切意味着堆栈的内存在堆中,而不是在Java执行堆栈中,但是这对于您有更多的控制权是有用的。





iteration