这取决于语言。在Java中，你应该使用循环。函数式语言优化递归。

使用递归，每次“迭代”都会产生函数调用的成本，而使用循环，你通常只需要支付递增/递减的代价。因此，如果循环的代码并不比递归解决方案的代码复杂多少，循环通常会优于递归。

我认为在(非尾)递归中，每当函数被调用时，分配一个新的堆栈等都会受到性能影响(当然取决于语言)。

递归的内存开销更大，因为每次递归调用通常都需要将一个内存地址推入堆栈，以便稍后程序可以返回到那个地址。

尽管如此，在许多情况下，递归比循环更自然、更可读——比如在处理树的时候。在这些情况下，我建议坚持使用递归。

通常情况下，人们会期望性能损失在另一个方向上。递归调用会导致构建额外的堆栈帧;对此的惩罚各不相同。此外，在一些语言中，如Python(更准确地说，是在某些语言的某些实现中……)，对于递归指定的任务，您可能很容易遇到堆栈限制，例如在树状数据结构中查找最大值。在这些情况下，你应该坚持使用循环。

编写好的递归函数可以在一定程度上降低性能损失，前提是你有一个优化尾部递归的编译器，等等(还要再次检查，确保函数真的是尾部递归——这是许多人都会犯的错误之一)。

除了“边缘”情况(高性能计算、非常大的递归深度等)之外，最好采用最清楚地表达您的意图、设计良好且可维护的方法。仅在确定需求后进行优化。

它取决于“递归深度”。 这取决于函数调用开销对总执行时间的影响程度 例如，以递归的方式计算经典阶乘是非常低效的，因为: —数据溢出风险 -栈溢出风险 -函数调用开销占执行时间的80%

同时开发一种最小-最大算法用于国际象棋游戏中的位置分析，该算法将分析后续的N步棋，可以在“分析深度”上以递归方式实现(正如我正在做的^_^)

递归可能会更昂贵，这取决于递归函数是否为尾递归(最后一行是递归调用)。尾递归应该将被编译器识别并优化为迭代对应对象(同时保持代码中简洁、清晰的实现)。

我将以最有意义的方式编写算法，并且对那些不得不在几个月或几年内维护代码的可怜的傻瓜(无论是你自己还是其他人)来说是最清楚的。如果你遇到了性能问题，那就分析你的代码，然后，只有在那之后，你才能通过迭代实现来进行优化。你可能想看看记忆有关和动态规划。

使用递归时性能会下降，因为在任何语言中，调用方法都意味着大量的准备工作:调用代码发布一个返回地址、调用参数、一些其他上下文信息，如处理器寄存器可能保存在某个地方，在返回时，被调用的方法发布一个返回值，然后由调用者检索，之前保存的任何上下文信息将被恢复。迭代和递归方法之间的性能差异在于这些操作所花费的时间。

从实现的角度来看，当处理调用上下文所需的时间与执行方法所需的时间相当时，您才真正开始注意到差异。如果递归方法的执行时间比调用上下文管理部分要长，那么就采用递归方法，因为代码通常更易于阅读和理解，而且不会注意到性能损失。否则，出于效率考虑，可以进行迭代。

我相信java中的尾递归目前还没有优化。详细信息散布在这关于LtU和相关链接的讨论中。它五月是即将到来的版本7的一个特性，但显然它在与堆栈检查结合时出现了某些困难，因为某些帧将丢失。自Java 2以来，堆栈检查一直用于实现他们的细粒度安全模型。

http://lambda-the-ultimate.org/node/1333

循环可以提高程序的性能。递归可以为程序员带来性能上的提升。在你的情况下，选择哪个更重要!

迈克说得对。尾部递归是由Java编译器或JVM优化出来的不。你总是会得到这样的堆栈溢出:

int count(int i) {
return i >= 100000000 ? i : count(i+1);
}

据我所知，Perl没有优化尾递归调用，但是您可以伪造它。

sub f{
my($l,$r) = @_;


if( $l >= $r ){
return $l;
} else {


# return f( $l+1, $r );


@_ = ( $l+1, $r );
goto &f;


}
}

第一次调用时，它将在堆栈上分配空间。然后它将改变它的参数，并重新启动子例程，而不向堆栈添加任何东西。因此，它会假装从未调用过自己，将其转变为一个迭代过程。

注意，这里没有“my @_;”或“local @_;”，如果你这样做了，它将不再工作。

递归和迭代取决于您想要实现的业务逻辑，尽管在大多数情况下可以互换使用。大多数开发人员选择递归，因为它更容易理解。

在很多情况下，它提供了比迭代方法更优雅的解决方案，常见的例子是遍历二叉树，所以它不一定更难维护。一般来说，迭代版本通常更快一些(在优化过程中可能会取代递归版本)，但递归版本更容易理解和正确实现。

递归在某些情况下非常有用。例如，考虑查找阶乘的代码

int factorial ( int input )
{
int x, fact = 1;
for ( x = input; x > 1; x--)
fact *= x;
return fact;
}

现在用递归函数来考虑这个问题

int factorial ( int input )
{
if (input == 0)
{
return 1;
}
return input * factorial(input - 1);
}

比较递归和迭代就像比较十字螺丝刀和一字螺丝刀。在大多数情况下，你可以移除任何一个平头的十字螺钉，但如果你使用为该螺钉设计的螺丝刀，它会更容易，对吗?

有些算法只是适合递归，因为它们的设计方式(斐波那契数列，遍历树状结构等)。递归使算法更简洁，更容易理解(因此可共享和可重用)。

此外，一些递归算法使用“惰性评估”，这使得它们比迭代算法更有效。这意味着它们只在需要的时候执行昂贵的计算，而不是每次循环运行时都执行。

这应该足够让你开始了。我也会给你找一些文章和例子。

链接1: Haskel vs PHP(递归vs迭代)

下面是一个程序员必须使用PHP处理大型数据集的示例。他展示了在Haskel中使用递归处理是多么容易，但由于PHP没有简单的方法来完成相同的方法，他被迫使用迭代来获得结果。

http://blog.webspecies.co.uk/2011-05-31/lazy-evaluation-with-php.html

链接2:掌握递归

递归的坏名声大多来自于命令式语言的高成本和低效率。本文的作者讨论了如何优化递归算法，使其更快、更有效。他还介绍了如何将传统循环转换为递归函数，以及使用尾部递归的好处。我认为他的结束语总结了我的一些要点:

"递归编程为程序员提供了一种更好的组织方式 以一种既可维护又逻辑一致的方式编写代码。" < / p >

https://developer.ibm.com/articles/l-recurs/

链接3:是递归比循环快吗?(回答)

下面是一个与你的问题类似的stackoverflow问题的答案链接。作者指出，许多与递归或循环相关的基准测试都是非常语言特定的。命令式语言通常使用循环更快，使用递归更慢，函数式语言反之亦然。我想从这个链接中得到的主要观点是，在语言不可知论/情境盲目的意义上回答这个问题是非常困难的。

是递归比循环快吗?< / >

递归?从哪里开始呢，维基会告诉你"这是以一种自相似的方式重复项目的过程"

在我做C语言的时候，c++的递归是上帝的恩赐，就像“尾递归”。您还会发现许多排序算法使用递归。快速排序示例:http://alienryderflex.com/quicksort/

递归就像任何其他算法一样，适用于特定的问题。也许你不能马上或经常找到一个用途，但会有问题，你会很高兴它可用。

如果你只是在一个列表上迭代，那么当然，迭代出去。

其他几个答案提到了(深度优先)树遍历。这真的是一个很好的例子，因为这是对一个非常普通的数据结构所做的非常普通的事情。对于这个问题，递归是非常直观的。

查看“find”方法: http://penguin.ewu.edu/cscd300/Topic/BSTintro/index.html < / p >

对于可以分解为多个，更小的问题，递归比迭代更好。

例如，要制作一个递归斐波那契算法，您将fib(n)分解为fib(n-1)和fib(n-2)，并计算这两部分。迭代只允许你一遍又一遍地重复一个函数。

然而，Fibonacci实际上是一个坏例子，我认为迭代实际上更有效。注意fib(n) = fib(n-1) + fib(n-2)和fib(n-1) = fib(n-2) + fib(n-3)。Fib (n-1)被计算了两次!

一个更好的例子是树的递归算法。分析父节点的问题可以分解为分析每个子节点的多个个小问题。与斐波那契例子不同，较小的问题是相互独立的。

所以，对于那些可以分解成多个、更小、独立、相似问题的问题，递归比迭代更好。

递归比迭代的任何可能定义都更简单(因此也更基本)。你可以只用组合子对定义一个图灵完备系统(是的，在这样的系统中，甚至递归本身也是一个衍生概念)。λ微积分是一个同样强大的基本系统，具有递归函数。但是如果你想正确地定义一个迭代，你需要更多的原语来开始。

至于代码——不，递归代码实际上比纯迭代代码更容易理解和维护，因为大多数数据结构都是递归的。当然，为了正确使用它，至少需要一种支持高阶函数和闭包的语言，以简洁的方式获得所有标准的组合子和迭代器。当然，在c++中，复杂的递归解看起来有点丑，除非你是FC + +的铁杆用户。

在许多情况下，由于缓存提高了性能，递归更快。例如，这是一个使用传统归并例程的归并排序的迭代版本。它将比递归实现运行得慢，因为缓存改进了性能。

迭代实现

public static void sort(Comparable[] a)
{
int N = a.length;
aux = new Comparable[N];
for (int sz = 1; sz < N; sz = sz+sz)
for (int lo = 0; lo < N-sz; lo += sz+sz)
merge(a, lo, lo+sz-1, Math.min(lo+sz+sz-1, N-1));
}

递归实现

private static void sort(Comparable[] a, Comparable[] aux, int lo, int hi)
{
if (hi <= lo) return;
int mid = lo + (hi - lo) / 2;
sort(a, aux, lo, mid);
sort(a, aux, mid+1, hi);
merge(a, aux, lo, mid, hi);
}

PS -这是Kevin Wayne教授(普林斯顿大学)在Coursera上的算法课程上讲的。

我将通过“归纳”设计一个Haskell数据结构来回答你的问题，这是递归的一种“对偶”。然后我会展示这种对偶性是如何带来好的结果的。

我们为简单树引入一个类型:

data Tree a = Branch (Tree a) (Tree a)
| Leaf a
deriving (Eq)

我们可以把这个定义理解为“一棵树是一个分支(包含两棵树)或一个叶子(包含一个数据值)”。叶结点是一种最小的情况。如果树不是叶子，那么它一定是包含两棵树的复合树。这些是唯一的例子。

让我们做一个树:

example :: Tree Int
example = Branch (Leaf 1)
(Branch (Leaf 2)
(Leaf 3))

现在，让我们假设我们想给树中的每个值加1。我们可以通过调用:

addOne :: Tree Int -> Tree Int
addOne (Branch a b) = Branch (addOne a) (addOne b)
addOne (Leaf a)     = Leaf (a + 1)

首先，请注意这实际上是一个递归定义。它将数据构造函数Branch和Leaf作为case(因为Leaf是最小值的，这是唯一可能的case)，我们可以确定函数将终止。

用迭代风格编写addOne需要什么?循环进入任意数量的分支会是什么样子?

此外，这种递归通常可以用“函子”来分解。我们可以通过定义将树变成函子:

instance Functor Tree where fmap f (Leaf a)     = Leaf (f a)
fmap f (Branch a b) = Branch (fmap f a) (fmap f b)

和定义:

addOne' = fmap (+1)

我们可以提出其他递归方案，例如代数数据类型的变形(或折叠)。使用变形法，我们可以这样写:

addOne'' = cata go where
go (Leaf a) = Leaf (a + 1)
go (Branch a b) = Branch a b

如果迭代是原子的，并且比推送一个新的堆栈框架而且创建一个新线程而且的成本要高几个数量级，那么你有多个内核而且，你的运行时环境可以使用所有这些内核，那么当与多线程结合时，递归方法可以产生巨大的性能提升。如果迭代的平均次数是不可预测的，那么使用线程池可能是一个好主意，它将控制线程分配，并防止进程创建太多线程并占用系统。

例如，在某些语言中，存在递归多线程归并排序实现。

但同样，多线程可以与循环而不是递归一起使用，因此这种组合的工作效果取决于更多因素，包括操作系统及其线程分配机制。

你必须记住，使用太深的递归，你会遇到堆栈溢出，这取决于允许的堆栈大小。为了防止这种情况，请确保提供一些基本情况，以结束递归。

使用Chrome 45.0.2454.85 m，递归似乎要快得多。

代码如下:

(function recursionVsForLoop(global) {
"use strict";


// Perf test
function perfTest() {}


perfTest.prototype.do = function(ns, fn) {
console.time(ns);
fn();
console.timeEnd(ns);
};


// Recursion method
(function recur() {
var count = 0;
global.recurFn = function recurFn(fn, cycles) {
fn();
count = count + 1;
if (count !== cycles) recurFn(fn, cycles);
};
})();


// Looped method
function loopFn(fn, cycles) {
for (var i = 0; i < cycles; i++) {
fn();
}
}


// Tests
var curTest = new perfTest(),
testsToRun = 100;


curTest.do('recursion', function() {
recurFn(function() {
console.log('a recur run.');
}, testsToRun);
});


curTest.do('loop', function() {
loopFn(function() {
console.log('a loop run.');
}, testsToRun);
});


})(window);

结果

//使用标准for循环运行100次

100x循环运行。 完成时间:7.683毫秒

//使用带有尾递归的函数递归方法运行100次

100x递归运行。 完成时间:4.841毫秒

在下面的截图中，当每次测试运行300次循环时，递归再次以更大的优势获胜

< / >

在c++中，如果递归函数是模板化的，那么编译器有更多的机会优化它，因为所有的类型推导和函数实例化都将在编译时发生。如果可能的话，现代编译器还可以内联函数。因此，如果在g++中使用像-O3或-O2这样的优化标志，那么递归可能有机会比迭代更快。在迭代代码中，编译器很少有机会优化它，因为它已经处于或多或少的最佳状态(如果写得足够好)。

iterative + optimisation flag -O3 -> 2.79.. sec
recursive + optimisation flag -O3 -> 1.32.. sec


iterative + No-optimisation flag  -> 2.83.. sec
recursive + No-optimisation flag  -> 4.15.. sec

这些结果是使用gcc-4.8与c++11标志(-std=c++11)和Armadillo 6.1与Intel mkl获得的。英特尔编译器也显示了类似的结果。

见下文。

有时使用递归编写算法更容易，而使用迭代编写相同的算法略难。在这种情况下，如果您选择遵循迭代方法，您将不得不自己处理堆栈。

堆栈溢出只会发生在编程语言没有内置内存管理....否则，请确保在函数(或函数调用、STDLbs等)中有一些内容。如果没有递归，就不可能有这样的东西……谷歌或SQL，或任何地方一个人必须有效地排序大型数据结构(类)或数据库。

如果你想要遍历文件，递归是一种方法，我敢肯定这就是find * | ?grep *的工作方式。有点像双重递归，特别是管道(但不要像很多人那样做一堆系统调用，如果你要把它放在那里供别人使用的话)。

高级语言，甚至clang/cpp也可以在后台实现相同的功能。

细节:

在递归的情况下，很容易创建前后遍历:

想象一个相当标准的问题:“当任务依赖于其他任务时，打印所有应该执行的任务以执行任务5”

例子:

    //key-task, value-list of tasks the key task depends on
//"adjacency map":
Map<Integer, List<Integer>> tasksMap = new HashMap<>();
tasksMap.put(0, new ArrayList<>());
tasksMap.put(1, new ArrayList<>());


List<Integer> t2 = new ArrayList<>();
t2.add(0);
t2.add(1);
tasksMap.put(2, t2);


List<Integer> t3 = new ArrayList<>();
t3.add(2);
t3.add(10);
tasksMap.put(3, t3);


List<Integer> t4 = new ArrayList<>();
t4.add(3);
tasksMap.put(4, t4);


List<Integer> t5 = new ArrayList<>();
t5.add(3);
tasksMap.put(5, t5);


tasksMap.put(6, new ArrayList<>());
tasksMap.put(7, new ArrayList<>());


List<Integer> t8 = new ArrayList<>();
t8.add(5);
tasksMap.put(8, t8);


List<Integer> t9 = new ArrayList<>();
t9.add(4);
tasksMap.put(9, t9);


tasksMap.put(10, new ArrayList<>());


//task to analyze:
int task = 5;




List<Integer> res11 = getTasksInOrderDftReqPostOrder(tasksMap, task);
System.out.println(res11);**//note, no reverse required**


List<Integer> res12 = getTasksInOrderDftReqPreOrder(tasksMap, task);
Collections.reverse(res12);//note reverse!
System.out.println(res12);


private static List<Integer> getTasksInOrderDftReqPreOrder(Map<Integer, List<Integer>> tasksMap, int task) {
List<Integer> result = new ArrayList<>();
Set<Integer> visited = new HashSet<>();
reqPreOrder(tasksMap,task,result, visited);
return result;
}


private static void reqPreOrder(Map<Integer, List<Integer>> tasksMap, int task, List<Integer> result, Set<Integer> visited) {


if(!visited.contains(task)) {
visited.add(task);
result.add(task);//pre order!
List<Integer> children = tasksMap.get(task);
if (children != null && children.size() > 0) {
for (Integer child : children) {
reqPreOrder(tasksMap,child,result, visited);
}
}
}
}


private static List<Integer> getTasksInOrderDftReqPostOrder(Map<Integer, List<Integer>> tasksMap, int task) {
List<Integer> result = new ArrayList<>();
Set<Integer> visited = new HashSet<>();
reqPostOrder(tasksMap,task,result, visited);
return result;
}


private static void reqPostOrder(Map<Integer, List<Integer>> tasksMap, int task, List<Integer> result, Set<Integer> visited) {
if(!visited.contains(task)) {
visited.add(task);
List<Integer> children = tasksMap.get(task);
if (children != null && children.size() > 0) {
for (Integer child : children) {
reqPostOrder(tasksMap,child,result, visited);
}
}
result.add(task);//post order!
}
}

注意，递归后序遍历不需要对结果进行后续反转。孩子先打印，你的任务最后打印。一切都很好。您可以执行递归的预顺序遍历(上面也显示了)，这将需要反转结果列表。

迭代方法并不那么简单!在迭代(一个堆栈)方法中，你只能做一个预排序遍历，所以你必须在最后反转结果数组:

    List<Integer> res1 = getTasksInOrderDftStack(tasksMap, task);
Collections.reverse(res1);//note reverse!
System.out.println(res1);


private static List<Integer> getTasksInOrderDftStack(Map<Integer, List<Integer>> tasksMap, int task) {
List<Integer> result = new ArrayList<>();
Set<Integer> visited = new HashSet<>();
Stack<Integer> st = new Stack<>();




st.add(task);
visited.add(task);


while(!st.isEmpty()){
Integer node = st.pop();
List<Integer> children = tasksMap.get(node);
result.add(node);
if(children!=null && children.size() > 0){
for(Integer child:children){
if(!visited.contains(child)){
st.add(child);
visited.add(child);
}
}
}
//If you put it here - it does not matter - it is anyway a pre-order
//result.add(node);
}
return result;
}

看起来很简单，不是吗?

但在一些面试中，这是一个陷阱。

这意味着:使用递归方法，您可以实现深度优先遍历，然后选择需要的前后顺序(只需更改“打印”的位置，在我们的示例中是“添加到结果列表”)。使用迭代(一个堆栈)方法，你可以很容易只做预序遍历，所以在需要先打印子节点的情况下(几乎所有需要从底部节点开始打印，向上)-你就麻烦了。如果你遇到了这个问题，你可以稍后反转，但这将是对你的算法的一个补充。如果面试官在看手表，这对你来说可能是个问题。有很多复杂的方法来进行迭代后序遍历，它们存在，但它们是不是简单的。例如:https://www.geeksforgeeks.org/iterative-postorder-traversal-using-stack/

因此，底线是:我会在面试中使用递归，这样更容易管理和解释。在任何紧急情况下，您都可以轻松地从前顺序遍历到后顺序遍历。在迭代中，你就没有那么灵活了。

我会使用递归，然后说:“好吧，但是迭代可以让我更直接地控制使用的内存，我可以很容易地测量堆栈大小，并禁止一些危险的溢出。”

递归的另一个优点——避免/注意图中的循环更简单。

例子(preudocode):

dft(n){
mark(n)
for(child: n.children){
if(marked(child))
explode - cycle found!!!
dft(child)
}
unmark(n)
}

把它写成递归，或者作为练习，可能会很有趣。

但是，如果要在生产中使用该代码，则需要考虑堆栈溢出的可能性。

尾递归优化可以消除堆栈溢出，但是您是否想要经历这样的麻烦，并且您需要知道您可以指望它在您的环境中进行优化。

每次算法递归时，数据大小或n减少了多少?

如果每次递归时都将data或n的大小减少一半，则通常不需要担心堆栈溢出。例如，如果程序堆栈溢出需要4,000层或10,000层深度，那么您的数据大小需要大致为2⁴⁰⁰⁰才能使程序堆栈溢出。从这个角度来看，最近最大的存储设备可以容纳2⁶¹字节，如果你有2⁶¹这样的设备，你只处理2¹²²的数据大小。如果你观察宇宙中的所有原子，估计它可能小于2⁸⁴。如果你需要处理宇宙中所有的数据，以及自宇宙诞生以来(估计是140亿年前)每一毫秒的状态，那么它可能只有2¹⁵³。因此，如果你的程序可以处理2⁴⁰⁰⁰单位的数据或n，你就可以处理宇宙中的所有数据，并且程序不会堆栈溢出。如果你不需要处理像2⁴⁰⁰⁰(一个4000位整数)这样大的数字，那么通常你不需要担心堆栈溢出。

然而，如果你每次递归都将数据或n的大小减小一个常数，那么当n仅仅变成20000时，你就会遇到堆栈溢出。也就是说，当n为1000时，程序运行良好，并且您认为程序很好，然后当将来的某个时候，当n为5000或20000时，程序堆栈溢出。

所以如果你有堆栈溢出的可能，试着让它成为一个迭代的解决方案。

"如果我们使用循环而不是 在算法中递归或反之，两者都可以达到相同的目的?

河内塔的递归实现:

def TowerOfHanoi(n , source, destination, auxiliary):
if n==1:
print ("Move disk 1 from source",source,"to destination",destination)
return
TowerOfHanoi(n-1, source, auxiliary, destination)
print ("Move disk",n,"from source",source,"to destination",destination)
TowerOfHanoi(n-1, auxiliary, destination, source)

相当短，很容易读。将其与对应的迭代TowerOfHanoi进行比较:

# Python3 program for iterative Tower of Hanoi
import sys
 

# A structure to represent a stack
class Stack:
# Constructor to set the data of
# the newly created tree node
def __init__(self, capacity):
self.capacity = capacity
self.top = -1
self.array = [0]*capacity
 

# function to create a stack of given capacity.
def createStack(capacity):
stack = Stack(capacity)
return stack
  

# Stack is full when top is equal to the last index
def isFull(stack):
return (stack.top == (stack.capacity - 1))
   

# Stack is empty when top is equal to -1
def isEmpty(stack):
return (stack.top == -1)
   

# Function to add an item to stack.
# It increases top by 1
def push(stack, item):
if(isFull(stack)):
return
stack.top+=1
stack.array[stack.top] = item
   

# Function to remove an item from stack.
# It decreases top by 1
def Pop(stack):
if(isEmpty(stack)):
return -sys.maxsize
Top = stack.top
stack.top-=1
return stack.array[Top]
   

# Function to implement legal
# movement between two poles
def moveDisksBetweenTwoPoles(src, dest, s, d):
pole1TopDisk = Pop(src)
pole2TopDisk = Pop(dest)
 

# When pole 1 is empty
if (pole1TopDisk == -sys.maxsize):
push(src, pole2TopDisk)
moveDisk(d, s, pole2TopDisk)
       

# When pole2 pole is empty
else if (pole2TopDisk == -sys.maxsize):
push(dest, pole1TopDisk)
moveDisk(s, d, pole1TopDisk)
       

# When top disk of pole1 > top disk of pole2
else if (pole1TopDisk > pole2TopDisk):
push(src, pole1TopDisk)
push(src, pole2TopDisk)
moveDisk(d, s, pole2TopDisk)
       

# When top disk of pole1 < top disk of pole2
else:
push(dest, pole2TopDisk)
push(dest, pole1TopDisk)
moveDisk(s, d, pole1TopDisk)
   

# Function to show the movement of disks
def moveDisk(fromPeg, toPeg, disk):
print("Move the disk", disk, "from '", fromPeg, "' to '", toPeg, "'")
   

# Function to implement TOH puzzle
def tohIterative(num_of_disks, src, aux, dest):
s, d, a = 'S', 'D', 'A'
   

# If number of disks is even, then interchange
# destination pole and auxiliary pole
if (num_of_disks % 2 == 0):
temp = d
d = a
a = temp
total_num_of_moves = int(pow(2, num_of_disks) - 1)
   

# Larger disks will be pushed first
for i in range(num_of_disks, 0, -1):
push(src, i)
   

for i in range(1, total_num_of_moves + 1):
if (i % 3 == 1):
moveDisksBetweenTwoPoles(src, dest, s, d)
   

else if (i % 3 == 2):
moveDisksBetweenTwoPoles(src, aux, s, a)
   

else if (i % 3 == 0):
moveDisksBetweenTwoPoles(aux, dest, a, d)
 

# Input: number of disks
num_of_disks = 3
 

# Create three stacks of size 'num_of_disks'
# to hold the disks
src = createStack(num_of_disks)
dest = createStack(num_of_disks)
aux = createStack(num_of_disks)
 

tohIterative(num_of_disks, src, aux, dest)

    if m == 0:
# BASE CASE
return n + 1
elif m > 0 and n == 0:
# RECURSIVE CASE
return ackermann(m - 1, 1)
elif m > 0 and n > 0:
# RECURSIVE CASE
return ackermann(m - 1, ackermann(m, n - 1))

使用迭代:

callStack = [{'m': 2, 'n': 3, 'indentation': 0, 'instrPtr': 'start'}]
returnValue = None


while len(callStack) != 0:
m = callStack[-1]['m']
n = callStack[-1]['n']
indentation = callStack[-1]['indentation']
instrPtr = callStack[-1]['instrPtr']


if instrPtr == 'start':
print('%sackermann(%s, %s)' % (' ' * indentation, m, n))


if m == 0:
# BASE CASE
returnValue = n + 1
callStack.pop()
continue
elif m > 0 and n == 0:
# RECURSIVE CASE
callStack[-1]['instrPtr'] = 'after first recursive case'
callStack.append({'m': m - 1, 'n': 1, 'indentation': indentation + 1, 'instrPtr': 'start'})
continue
elif m > 0 and n > 0:
# RECURSIVE CASE
callStack[-1]['instrPtr'] = 'after second recursive case, inner call'
callStack.append({'m': m, 'n': n - 1, 'indentation': indentation + 1, 'instrPtr': 'start'})
continue
elif instrPtr == 'after first recursive case':
returnValue = returnValue
callStack.pop()
continue
elif instrPtr == 'after second recursive case, inner call':
callStack[-1]['innerCallResult'] = returnValue
callStack[-1]['instrPtr'] = 'after second recursive case, outer call'
callStack.append({'m': m - 1, 'n': returnValue, 'indentation': indentation + 1, 'instrPtr': 'start'})
continue
elif instrPtr == 'after second recursive case, outer call':
returnValue = returnValue
callStack.pop()
continue
print(returnValue)

再说一次，递归实现更容易理解。所以我的结论是，如果问题本质上是递归的，需要操作堆栈中的项，就使用递归。