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

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

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

这是为了在没有细节的情况下展示想法。考虑这个函数，它将打印出图的节点:

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 > C - > show(A)将打印B, A, C

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

例如，假设show(A)开始运行。函数调用在第3行。显示(B)的意思 -将项目添加到堆栈，意思是“你需要在第2行继续使用本地变量状态node=A” —到第0行，节点为B。

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

想想那些真正需要堆栈的东西:

如果我们考虑递归的模式为:

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执行堆栈中，但这可能很有用，因为您可以更好地控制它。

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

即使使用堆栈也不能将递归算法转换为迭代算法。普通的递归是基于函数的递归，如果我们使用堆栈，那么它就变成了基于堆栈的递归。但它仍然是递归。

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

但是如果我们使用堆栈的话复杂度还是一样的。我认为只有尾递归可以转化为迭代。

我的例子是用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)))))