在我多年的编程生涯中,我经常使用递归来解决简单的问题,但我完全意识到,有时由于内存/速度问题,您需要迭代。

所以,在很久以前的某个时候,我去尝试寻找是否存在任何“模式”或教科书上的方法来将常见的递归方法转换为迭代,但一无所获。至少我想不起有什么帮助。

有一般的规则吗? 有“模式”吗?


当前回答

通常避免栈溢出的技术是递归函数,称为蹦床技术,被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);
}

其他回答

我的例子是用Clojure编写的,但是应该很容易翻译成任何语言。

给定这个函数,当n值较大时StackOverflows:

(defn factorial [n]
  (if (< n 2)
    1
    (*' n (factorial (dec n)))))

我们可以用以下方式定义一个使用自己堆栈的版本:

(defn factorial [n]
  (loop [n n
         stack []]
    (if (< n 2)
      (return 1 stack)
      ;; else loop with new values
      (recur (dec n)
             ;; push function onto stack
             (cons (fn [n-1!]
                     (*' n n-1!))
                   stack)))))

其中return定义为:

(defn return
  [v stack]
  (reduce (fn [acc f]
            (f acc))
          v
          stack))

这也适用于更复杂的函数,例如阿克曼函数:

(defn ackermann [m n]
  (cond
    (zero? m)
    (inc n)

    (zero? n)
    (recur (dec m) 1)

    :else
    (recur (dec m)
           (ackermann m (dec n)))))

可以转化为:

(defn ackermann [m n]
  (loop [m m
         n n
         stack []]
    (cond
      (zero? m)
      (return (inc n) stack)

      (zero? n)
      (recur (dec m) 1 stack)

      :else
      (recur m
             (dec n)
             (cons #(ackermann (dec m) %)
                   stack)))))

只是消磨时间……递归函数

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

}

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

在谷歌中搜索“延续传递样式”。有一个转换为尾部递归样式的一般过程;还有一个将尾部递归函数转换为循环的通用过程。

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

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