了解recursion函数如何工作

正如标题所解释的，我有一个非常基本的编程问题，我还没有find。 过滤掉所有（非常聪明的）“为了理解recursion，你必须先理解recursion。” 来自各种线上线程的回复我还是不太明白。

了解到在面对不知道我们不知道的事情的时候，我们可能会倾向于提出错误的问题或不正确地提出正确的问题。我将分享我所“想”的问题，希望有相似前景的人可以分享一些一点点的知识，将帮助打开我的recursion灯泡！

这里是函数（语法是用Swift编写的）：

func sumInts(a: Int, b: Int) -> Int { if (a > b) { return 0 } else { return a + sumInts(a: a + 1, b: b) } } 

我们将使用2和5作为我们的参数：

 println(sumInts(a: 2, b: 5)) 

显然答案是14，但我不清楚如何实现这个价值。

这是我的两个挂断：

1. recursion调用该函数直到满足条件。 那个条件是a> b。 当这个条件满足时，返回0.乍一看，我期望返回值为0，这显然是不正确的。

2. 在每次迭代中打印出'a'的值就会得到一个我期望的值：2,3,4,5（在满足第一个条件的a + b> 5 + 1> b的情况下）看看14的价值是如何实现的。

我的第一个想法是，神奇地发生了类似于以下的事情：

 var answer = a; answer += a+1 until a > b; return answer; 

所以排除魔法，我只是没有得到什么。 我很想知道发生了什么，而不仅仅是隐含的。

如果有人能够很好的解释这种function在技术上发生了什么，为什么结果不是0以及最后怎么a + sumInts(a: a + 1, b: b) = 14 ，我会永远在你的债务。

Answer 1

我认为这种混淆是因为它被认为是多次被称为“相同的function”。 如果你认为它是“被调用的同一函数的许多副本”，那么可能会更清楚：

只有函数的一个副本返回0，它不是第一个（这是最后一个）。 所以调用第一个的结果不是0。

对于第二点混淆，我认为用英文说明recursion会容易一些。 阅读这一行：

 return a + sumInts(a + 1, b: b) 

作为“返回值的一个”加“（函数的另一个副本的返回值，它是”a“的副本的值加上（该函数的另一个副本的返回值，这是第二个副本的值'一个“加（…）”，函数的每个副本产生一个新的副本，自增1，直到a> b条件满足。

当你达到a> b的条件时，你有一个（可能是任意的）函数拷贝的堆栈正在运行中，所有等待下一个拷贝的结果来找出它们是什么应该加上'a'。

（编辑：另外，需要注意的是，我提到的这个函数的堆栈是一个真实的东西，它会占用真实的内存，如果程序太大，会导致程序崩溃，编译器可以优化它情况，但是耗尽堆栈空间是许多语言中recursion函数的显着和不幸的限制）

Answer 2

1.函数被recursion地调用，直到满足条件。 那个条件是a > b 。 当这个条件满足时，返回0.乍一看，我期望返回值为0，这显然是不正确的。

计算机计算sumInts(2,5)如果能够：

 I want to compute sumInts(2, 5) for this, I need to compute sumInts(3, 5) and add 2 to the result. I want to compute sumInts(3, 5) for this, I need to compute sumInts(4, 5) and add 3 to the result. I want to compute sumInts(4, 5) for this, I need to compute sumInts(5, 5) and add 4 to the result. I want to compute sumInts(5, 5) for this, I need to compute sumInts(6, 5) and add 5 to the result. I want to compute sumInts(6, 5) since 6 > 5, this is zero. The computation yielded 0, therefore I shall return 5 = 5 + 0. The computation yielded 5, therefore I shall return 9 = 4 + 5. The computation yielded 9, therefore I shall return 12 = 3 + 9. The computation yielded 12, therefore I shall return 14 = 2 + 12. 

正如你看到的，一些调用函数sumInts实际上返回0然而这不是最终值，因为计算机仍然必须添加5到0，然后是4结果，然后是3，然后是2，如最后四个句子我们电脑的想法。 请注意，在recursion中，计算机不仅要计算recursion调用，还必须记住recursion调用返回的值。 计算机的内存有一个特殊的区域，称为堆栈 ，这种信息被保存起来，这个空间是有限的，recursion的函数会耗尽堆栈：这是堆栈溢出 ，它的名字给我们最喜欢的网站。

你的陈述似乎隐含了一个假设，即计算机忘记了recursion调用时的情况，但这并不是，这就是为什么你的结论与你的观察不符。

2.在每次迭代中打印出'a'的值就会得到一个我期望得到的值：2,3,4,5（在满足第一个条件的a + b> 5 + 1> b的情况下）没有看到14的价值是如何实现的。

这是因为返回值不是a本身，而是a的值和recursion调用返回的值之和。

Answer 3

为了理解recursion，你必须以不同的方式来思考问题。 而不是一个整体上合理的步骤的大逻辑顺序，而是采取一个大问题，分解成较小的问题，并解决这些问题，一旦你有一个问题的答案你结合子问题的结果，使解决更大的问题。 想想你和你的朋友需要计算一个巨大的桶里的弹珠数量。 你们每个人都要拿一个小桶去计算这些个体，当你们完成后，把总数加起来。现在，如果你们每个人都find了一些朋友，并进一步分配桶，那么你只需要等待这些其他的朋友找出他们的总数，把它带回给你们每个人，你把它加起来。 等等。 特殊的情况是，当你只有1个大理石的数量，然后你只是返回，并说1。让其他人在你上面做添加你完成。

您必须记住，每次函数recursion调用它时，都会创build一个带有问题子集的新上下文，一旦解决了这个问题，它就会返回，以便前一个迭代可以完成。

让我告诉你的步骤：

 sumInts(a: 2, b: 5) will return: 2 + sumInts(a: 3, b: 5) sumInts(a: 3, b: 5) will return: 3 + sumInts(a: 4, b: 5) sumInts(a: 4, b: 5) will return: 4 + sumInts(a: 5, b: 5) sumInts(a: 5, b: 5) will return: 5 + sumInts(a: 6, b: 5) sumInts(a: 6, b: 5) will return: 0 

一旦总数（a：6，b：5）执行完毕，结果就可以计算出来，从而得出结果：

  sumInts(a: 6, b: 5) = 0 sumInts(a: 5, b: 5) = 5 + 0 = 5 sumInts(a: 4, b: 5) = 4 + 5 = 9 sumInts(a: 3, b: 5) = 3 + 9 = 12 sumInts(a: 2, b: 5) = 2 + 12 = 14. 

表示recursion结构的另一种方法是：

  sumInts(a: 2, b: 5) = 2 + sumInts(a: 3, b: 5) sumInts(a: 2, b: 5) = 2 + 3 + sumInts(a: 4, b: 5) sumInts(a: 2, b: 5) = 2 + 3 + 4 + sumInts(a: 5, b: 5) sumInts(a: 2, b: 5) = 2 + 3 + 4 + 5 + sumInts(a: 6, b: 5) sumInts(a: 2, b: 5) = 2 + 3 + 4 + 5 + 0 sumInts(a: 2, b: 5) = 14 

Answer 4

recursion是一个棘手的话题要理解，我不认为我可以在这里完全做到这一点。 相反，我会试着把注意力集中在你在这里的特定代码上，并试图描述解决scheme为什么运作的直觉以及代码如何计算结果的机制。

你在这里给出的代码解决了以下问题：你想知道从a到b的所有整数的和。 对于你的例子，你想要的总和数字从2到5，包括，这是

2 + 3 + 4 + 5

当试图recursion地解决一个问题时，首先应该找出如何将问题分解成具有相同结构的较小问题。 因此，假设你想总结从2到5的数字。 一种简单的方法是注意上面的总和可以被重写为

2 +（3 + 4 + 5）

这里，（3 + 4 + 5）恰好是3和5之间的所有整数的和。 换句话说，如果你想知道2和5之间的所有整数的总和，首先计算3和5之间的所有整数的和，然后加2。

那么你如何计算3到5之间的所有整数的和？ 那么，这个数字是

3 + 4 + 5

这可以被认为是相反的

3 +（4 + 5）

这里，（4 + 5）是4和5之间的所有整数的和。 所以，如果你想计算3和5之间的所有数字的总和（包括3和5），你可以计算4和5之间的所有整数的总和，然后加3。

这里有一个模式！ 如果要计算a和b（包含）之间的整数之和，可以执行以下操作。 首先，计算a + 1和b之间的整数之和（包含）。 接下来，添加一个到这个总数。 你会注意到“计算a + 1和b之间的整数之和，包括”包含在内“恰好与我们已经试图解决的问题几乎是一样的，但是参数略有不同。 而不是从a到b的计算，包括在内，我们计算从+1到b（含）。 这是recursion的步骤 – 为了解决更大的问题（“从a到b，包容性”），我们将问题简化为自身的一个较小的版本（“从a + 1到b，包括的总和”）。

如果你看看上面的代码，你会注意到它有这个步骤：

 return a + sumInts(a + 1, b: b) 

这个代码只是上面的逻辑的翻译 – 如果你想从a到b（包含），总结a + 1到b（包括sumInt的recursion调用），然后添加a 。

当然，这种方法本身实际上不会起作用。 例如，你将如何计算5和5之间的所有整数的和？ 那么，使用我们当前的逻辑，你将计算6和5之间的所有整数的总和，然后加5，那么你如何计算6和5之间的所有整数的和？ 那么，使用我们当前的逻辑，你可以计算所有整数在7和5之间（包括7和5）的总和，然后加6.你会注意到一个问题 – 这只是继续前进！

在recursion问题解决中，需要有一些方法来停止简化问题，而是直接解决问题。 通常情况下，你会发现一个简单的情况，可以立即确定答案，然后构build解决scheme，直接解决简单的情况。 这通常被称为基本情况或recursion基础 。

那么这个特定问题的基本情况是什么呢？ 当你总结从a到b的整数时，如果碰巧比b大，那么答案是0–在范围内没有任何数字！ 因此，我们将构build我们的解决scheme如下：

1. 如果a> b，那么答案是0。
2. 否则（a≤b），得到答案如下：
   1. 计算a + 1和b之间的整数之和。
   2. 添加一个来得到答案。

现在，比较这个伪代码到你的实际代码：

 func sumInts(a: Int, b: Int) -> Int { if (a > b) { return 0 } else { return a + sumInts(a + 1, b: b) } } 

请注意，在伪代码和这个实际的代码之间几乎完全是一对一的映射。 第一步是基本情况 – 如果您要求空数字范围的总和，则得到0.否则，计算a + 1和b之间的和，然后加上a。

到目前为止，我已经给出了代码背后的一个高层次的想法。 但是你还有另外两个非常好的问题。 首先，为什么不总是返回0，假设函数说如果a> b返回0？ 其次，14实际上从哪里来？ 我们来看看这些。

我们来尝试一个非常非常简单的例子。 如果你打电话给sumInts(6, 5)怎样？ 在这种情况下，通过代码追踪，你会发现该函数只返回0。这是正确的做法，在范围内没有任何数字。 现在，尝试一些更难的东西。 当你打电话给sumInts(5, 5)时会发生什么？ 那么，这是发生了什么事情：

1. 你叫sumInts(5, 5) 。 我们落入else分支，返回`a + sumInts（6，5）的值。
2. 为了让sumInts(5, 5)决定什么sumInts(6, 5) ，我们需要暂停我们正在做的事情，然后打电话给sumInts(6, 5) 。
3. sumInts(6, 5)被调用。 它进入if分支并返回0 。 然而， sumInts这个实例被sumInts调用sumInts(5, 5) ，所以返回值被传回给sumInts(5, 5) ，而不是传给顶级调用者。
4. sumInts(5, 5)现在可以计算5 + sumInts(6, 5)以得到5 。 然后将其返回给顶级调用者。

注意这里的价值5是如何形成的。 我们开始了一个积极的呼吁sumInts 。 这发射了另一个recursion调用，并且该调用返回的值将信息传回给sumInts(5, 5) 。 然后对sumInts(5, 5)的调用进行一些计算，并将值返回给调用者。

如果你用sumInts(4, 5)试试这个，会发生什么：

• sumInts(4, 5)试图返回4 + sumInts(5, 5) 。 为此，它调用sumInts(5, 5) 。
  • sumInts(5, 5)试图返回5 + sumInts(6, 5) 。 为此，它调用sumInts(6, 5) 。
  • sumInts(6, 5)返回0到sumInts(5, 5).</li> <li> 。sumInts（5,5） now has a value for sumInts（6,5） now has a value for , namely 0. It then returns 5 + 0 = 5`。
• sumInts(4, 5)现在具有sumInts(4, 5)的值，即5，然后返回4 + 5 = 9 。

换句话说，返回的值是通过一次一个地求和来形成的，每次将一个特定的recursion调用返回的值传递给sumInts并且加上a的当前值。 当recursion降到最低时，最深的调用返回0.但是，该值不会立即退出recursion调用链; 相反，它只是把值递回到它上面的recursion调用层。 这样，每个recursion调用只需要添加一个数字，并在链中返回更高的值，最后总结。 作为一个练习，试着找出sumInts(2, 5) ，这就是你想要开始的。

希望这可以帮助！

Answer 5

到目前为止，你已经得到了一些很好的答案，但是我会再添加一个不同的方法。

首先，我写了许多关于简单recursionalgorithm的文章，您可能会感兴趣; 看到

http://ericlippert.com/tag/recursion/

http://blogs.msdn.com/b/ericlippert/archive/tags/recursion/

那些在最新的订单，所以从头开始。

其次，到目前为止，所有的答案都通过考虑函数激活来描述recursion语义。 每个调用都会进行一次新的激活 ，recursion调用将在激活的上下文中执行。 这是一个很好的思考方式，但还有另一种等同的方式： 聪明的文本search和replace 。

让我把你的函数改写成稍微紧凑的forms; 不要认为这是任何特定的语言。

 s = (a, b) => a > b ? 0 : a + s(a + 1, b) 

我希望这是有道理的。 如果你对条件运算符不熟悉，它是否是formscondition ? consequence : alternative condition ? consequence : alternative ，它的意义将变得清晰。

现在我们希望评估s(2,5)我们通过用函数体replace掉文本，然后用2和b代替5 ：

 s(2, 5) ---> 2 > 5 ? 0 : 2 + s(2 + 1, 5) 

现在评估条件。 我们用falsereplace2 > 5 。

 ---> false ? 0 : 2 + s(2 + 1, 5) 

现在用文本replace所有的假条件和替代条件以及所有的真条件。 我们只有错误的条件，所以我们用另一个文本replace这个expression式：

 ---> 2 + s(2 + 1, 5) 

现在，为了节省我不得不input所有这些+符号，在文本上用常数算术replace它的值。 （这有点欺骗，但我不想跟踪所有的括号！）

 ---> 2 + s(3, 5) 

现在search和replace，这次与电话的身体， 3为a和5为b。 我们将把replace的电话放在括号里：

 ---> 2 + (3 > 5 ? 0 : 3 + s(3 + 1, 5)) 

现在我们继续进行相同的文本replace步骤：

 ---> 2 + (false ? 0 : 3 + s(3 + 1, 5)) ---> 2 + (3 + s(3 + 1, 5)) ---> 2 + (3 + s(4, 5)) ---> 2 + (3 + (4 > 5 ? 0 : 4 + s(4 + 1, 5))) ---> 2 + (3 + (false ? 0 : 4 + s(4 + 1, 5))) ---> 2 + (3 + (4 + s(4 + 1, 5))) ---> 2 + (3 + (4 + s(5, 5))) ---> 2 + (3 + (4 + (5 > 5 ? 0 : 5 + s(5 + 1, 5)))) ---> 2 + (3 + (4 + (false ? 0 : 5 + s(5 + 1, 5)))) ---> 2 + (3 + (4 + (5 + s(5 + 1, 5)))) ---> 2 + (3 + (4 + (5 + s(6, 5)))) ---> 2 + (3 + (4 + (5 + (6 > 5 ? 0 : s(6 + 1, 5))))) ---> 2 + (3 + (4 + (5 + (true ? 0 : s(6 + 1, 5))))) ---> 2 + (3 + (4 + (5 + 0))) ---> 2 + (3 + (4 + 5)) ---> 2 + (3 + 9) ---> 2 + 12 ---> 14 

我们在这里所做的只是直接的文本替代 。 真的我不应该用“3”代替“2 + 1”等等，直到我不得不去做，但是在教学上它会变得难以阅读。

函数激活只不过是将函数调用replace为调用的主体，并将forms参数replace为相应的参数。 你必须小心谨慎地引入括号，但除此之外，它只是文本replace。

当然，大多数语言实际上并没有实现激活作为文本replace，但逻辑上 ，这就是它。

那么什么是无限recursion呢？ 一个recursion的文本替代不停止！ 注意我们最终如何到达了一个没有更多s替代的步骤，然后我们可以将algorithm应用于规则。

Answer 6

我通常会弄清楚recursion函数是如何工作的，通过查看基本情况和反向工作。 这是应用于此function的技术。

首先是基本情况：

 sumInts(6, 5) = 0 

然后在调用堆栈上面的那个调用 ：

 sumInts(5, 5) == 5 + sumInts(6, 5) sumInts(5, 5) == 5 + 0 sumInts(5, 5) == 5 

然后在调用堆栈上面的那个调用：

 sumInts(4, 5) == 4 + sumInts(5, 5) sumInts(4, 5) == 4 + 5 sumInts(4, 5) == 9 

等等：

 sumInts(3, 5) == 3 + sumInts(4, 5) sumInts(3, 5) == 3 + 9 sumInts(3, 5) == 12 

等等：

 sumInts(2, 5) == 2 + sumInts(3, 5) sumInts(4, 5) == 2 + 12 sumInts(4, 5) == 14 

请注意， 我们已经到达了函数 sumInts(2, 5) == 14 原始调用

这些调用的执行顺序：

 sumInts(2, 5) sumInts(3, 5) sumInts(4, 5) sumInts(5, 5) sumInts(6, 5) 

这些调用返回的顺序：

 sumInts(6, 5) sumInts(5, 5) sumInts(4, 5) sumInts(3, 5) sumInts(2, 5) 

请注意，我们通过跟踪调用返回的顺序来得出关于函数如何操作的结论。

Answer 7

我会给它一个。

执行方程a + sumInts（a + 1，b），我将显示最终答案是14。

 //the sumInts function definition func sumInts(a: Int, b: Int) -> Int { if (a > b) { return 0 } else { return a + sumInts(a + 1, b) } } Given: a = 2 and b = 5 1) 2 + sumInts(2+1, 5) 2) sumInts(3, 5) = 12 i) 3 + sumInts(3+1, 5) ii) 4 + sumInts(4+1, 5) iii) 5 + sumInts(5+1, 5) iv) return 0 v) return 5 + 0 vi) return 4 + 5 vii) return 3 + 9 3) 2 + 12 = 14. 

如果您还有其他问题，请告诉我们。

下面的例子是recursion函数的另一个例子。

一个男人刚刚大学gradle。

吨是几年的时间。

退休前工作的实际总年数可以计算如下：

 public class DoIReallyWantToKnow { public int howLongDoIHaveToWork(int currentAge) { const int DESIRED_RETIREMENT_AGE = 65; double collectedMoney = 0.00; //remember, you just graduated college double neededMoneyToRetire = 1000000.00 t = 0; return work(t+1); } public int work(int time) { collectedMoney = getCollectedMoney(); if(currentAge >= DESIRED_RETIREMENT_AGE && collectedMoney == neededMoneyToRetire { return time; } return work(time + 1); } } 

而这应该足以压制任何人，哈哈。 ;-P

Answer 8

recursion。 在计算机科学中，recursion在有限自动机的主题下得到了深入的研究。

最简单的forms是一个自我参照。 例如，说“我的车是汽车”是一个recursion的陈述。 问题是这个陈述是一个无限的recursion，因为它永远不会结束。 在“汽车”的声明中的定义是，它是一个“汽车”，所以它可以被替代。 但是，由于在替代的情况下，它仍然是“我的车就是一辆车”。

如果声明是“我的车是宾利，我的车是蓝色的”，这可能会有所不同。 在这种情况下，在第二种情况下替代汽车可能是“宾利”，导致“我的宾利是蓝色的”。 这些types的replace在计算机科学中通过上下文无关文法进行了math解释。

实际替代是一个生产规则。 鉴于声明由S表示，并且该汽车是可以是“宾利”的variables，则该声明可以recursion地重构。

 S -> "my"S | " "S | CS | "is"S | "blue"S | ε C -> "bentley" 

这可以通过多种方式来构build，如每个| 意味着有一个select。 S可以被这些select中的任何一个取代，并且S总是空着的。 ε意味着终止生产。 就像S可以被replace一样，其他variables（只有一个，它代表“bentley”的C也可以被replace。

因此，以S为空，并以第一select"my"S S取代它成为

 "my"S 

S仍然可以代替，因为它代表一个variables。 我们可以select“我的”，或者结束它，但是让我们继续做我们原来的陈述吧。 我们selectS代替" "S的空间

 "my "S 

接下来让我们selectC

 "my "CS 

而C只有一个select来replace

 "my bentley"S 

再次为S的空间

 "my bentley "S 

等等"my bentley is"S "my bentley is "S "my bentley is blue"S "my bentley is blue" （用ε代替S结束生产），我们recursion地build立了”我的宾利是蓝色的“。

将recursion看作是这些生产和replace。 该过程中的每一步都会replace其前任，以产生最终结果。 在从2到5的recursion总和的确切示例中，最终生成

 S -> 2 + A A -> 3 + B B -> 4 + C C -> 5 + D D -> 0 

这成为

 2 + A 2 + 3 + B 2 + 3 + 4 + C 2 + 3 + 4 + 5 + D 2 + 3 + 4 + 5 + 0 14 

Answer 9

我认为理解recursion函数的最好方法是意识到它们是用来处理recursion数据结构的。 但是在原始函数sumInts(a: Int, b: Int)中recursion计算从a到b的数字之和，似乎不是一个recursion数据结构…让我们尝试稍微修改后的版本sumInts(a: Int, n: Int)其中n是您要添加的数字。

现在，sumInts是recursion的， n是一个自然数。 仍然不是一个recursion的数据，对不对？ 那么，自然数可以被认为是一个使用Peano公理的recursion数据结构：

 enum Natural = { case Zero case Successor(Natural) } 

所以，0 =零，1 = Succesor（零），2 = Succesor（Succesor（零）），等等。

一旦你有一个recursion的数据结构，你有这个函数的模板。 对于每个非recursion的情况，你可以直接计算出这个值。 对于recursion的情况， 你假定recursion函数已经在工作，并用它来计算大小写，但解构参数。 在自然的情况下，这意味着，而不是Succesor(n)我们将使用n ，或等价地，而不是n我们将使用n - 1 。

 // sums n numbers beginning from a func sumInts(a: Int, n: Int) -> Int { if (n == 0) { // non recursive case } else { // recursive case. We use sumInts(..., n - 1) } } 

现在recursion函数编程更简单。 首先是基本情况， n=0 。 如果我们不想添加数字，我们应该返回什么？ 答案当然是0。

那么recursion的情况呢？ 如果我们想要添加n以a开头的数字，而且我们已经有了一个可用于n-1 sumInts函数？ 那么，我们需要添加a ，然后用a + 1调用sumInts ，所以我们结束：

 // sums n numbers beginning from a func sumInts(a: Int, n: Int) -> Int { if (n == 0) { return 0 } else { return a + sumInts(a + 1, n - 1) } } 

好的是，现在你不需要考虑recursion的低级别。 你只需要validation：

• 对于recursion数据的基本情况，它不使用recursion计算答案。
• 对于recursion数据的recursion情况，它使用recursion在解构数据上计算答案。

Answer 10

您可能会对Nisan和Schocken的函数实现感兴趣。 链接的pdf是免费在线课程的一部分。 它描述了虚拟机实现的第二部分，学生应该编写一个虚拟机器语言到机器语言的编译器。 他们提出的函数实现能够recursion，因为它是基于堆栈的。

向您介绍函数实现：考虑以下虚拟机代码：

如果Swift编译成这个虚拟机的语言，那么下面的Swift代码块：

 mult(a: 2, b: 3) - 4 

将编译到

 push constant 2 // Line 1 push constant 3 // Line 2 call mult // Line 3 push constant 4 // Line 4 sub // Line 5 

虚拟机语言是围绕全局堆栈devise的。 push constant n将一个整数推送到这个全局堆栈上。

执行第1行和第2行之后，堆栈如下所示：

 256: 2 // Argument 0 257: 3 // Argument 1 

256和257是内存地址。

call mult将返回行号（3）推入堆栈并为函数的局部variables分配空间。

 256: 2 // argument 0 257: 3 // argument 1 258: 3 // return line number 259: 0 // local 0 

…并转到标签function mult 。 mult内的代码被执行。 作为执行该代码的结果，我们计算存储在函数的第0个局部variables中的2和3的乘积。

 256: 2 // argument 0 257: 3 // argument 1 258: 3 // return line number 259: 6 // local 0 

在从mult return之前，您会注意到这一行：

 push local 0 // push result 

We will push the product onto the stack.

 256: 2 // argument 0 257: 3 // argument 1 258: 3 // return line number 259: 6 // local 0 260: 6 // product 

When we return, the following happens:

• Pop the last value on the stack to the memory address of the 0th argument (256 in this case). This happens to be the most convenient place to put it.
• Discard everything on the stack up to the address of the 0th argument.
• Go-to the return line number (3 in this case) and then advance.

After returning we are ready to execute line 4, and our stack looks like this:

 256: 6 // product that we just returned 

Now we push 4 onto the stack.

 256: 6 257: 4 

sub is a primitive function of the virtual machine language. It takes two arguments and returns its result in the usual address: that of the 0th argument.

Now we have

 256: 2 // 6 - 4 = 2 

Now that you know how a function call works, it is relatively simple to understand how recursion works. No magic , just a stack.

I have implemented your sumInts function in this virtual machine language:

 function sumInts 0 // `0` means it has no local variables. label IF push argument 0 push argument 1 lte if-goto ELSE_CASE push constant 0 return label ELSE_CASE push constant 2 push argument 0 push constant 1 add push argument 1 call sumInts // Line 15 add // Line 16 return // Line 17 // End of function 

Now I will call it:

 push constant 2 push constant 5 call sumInts // Line 21 

The code executes and we get all the way to the stopping point where lte returns false . This is what the stack looks like at this point:

 // First invocation 256: 2 // argument 0 257: 5 // argument 1 258: 21 // return line number 259: 2 // augend // Second 260: 3 // argument 0 261: 5 // argument 1 262: 15 // return line number 263: 3 // augend // Third 264: 4 // argument 0 265: 5 // argument 1 266: 15 // return line number 267: 4 // augend // Fourth 268: 5 // argument 0 269: 5 // argument 1 270: 15 // return line number 271: 5 // augend // Fifth 272: 6 // argument 0 273: 5 // argument 1 274: 15 // return line number 275: 0 // return value 

Now let's "unwind" our recursion. return 0 and goto line 15 and advance.

 271: 5 272: 0 

Line 16: add

 271: 5 

Line 17: return 5 and goto line 15 and advance.

 267: 4 268: 5 

Line 16: add

 267: 9 

Line 17: return 9 and goto line 15 and advance.

 263: 3 264: 9 

Line 16: add

 263: 12 

Line 17: return 12 and goto line 15 and advance.

 259: 2 260: 12 

Line 16: add

 259: 14 

Line 17: return 14 and goto line 21 and advance.

 256: 14 

你有它。 Recursion: Glorified goto .

Answer 11

One really good tip I came across in learning and really understanding recursion is to spend some time learning a language that doesn't have any form of loop construct other than via recursion. That way you'll get a great feel for how to USE recursion via practice.

I followed http://www.htdp.org/ which, as well as being a Scheme tutorial, is also a great introduction on how to design programs in terms of the architecture and design.

But basically, you need to invest some time. Without a 'firm' grasp of recursion certain algorithms, such as backtracking, will always seem 'hard' or even 'magic' to you. So, persevere. 😀

I hope this helps and Good Luck!

Answer 12

There are already a lot of good answers. Still I am giving a try.
When called, a function get a memory-space allotted, which is stacked upon the memory-space of the caller function. In this memory-space, the function keeps the parameters passed to it, the variables and their values. This memory-space vanishes along with the ending return call of the function. As the idea of stack goes, the memory-space of the caller function now becomes active.

For recursive calls, the same function gets multiple memory-space stacked one upon another. 就这样。 The simple idea of how stack works in memory of a computer should get you through the idea of how recursion happens in implementation.

Answer 13

A little bit off-topic, I know, but… try looking up recursion in Google… You'll see by example what it means 🙂

---

Earlier versions of Google returned the following text (cited from memory):

recursion

See Recursion

On September 10th 2014, the joke about recursion has been updated:

recursion

Did you mean: Recursion

---

For another reply, see this answer .

Answer 14

Think recursion as a multiple clones doing same thing…

You ask to clone[1]: "sum numbers between 2 and 5"

 + clone[1] knows that: result is 2 + "sum numbers between 3 and 5". so he asks to clone[2] to return: "sum numbers between 3 and 5" | + clone[2] knows that: result is 3 + "sum numbers between 4 and 5". so he asks to clone[3] to return: "sum numbers between 4 and 5" | | + clone[3] knows that: result is 4 + "sum numbers between 5 and 5". so he asks to clone[4] to return: "sum numbers between 5 and 5" | | | + clone[4] knows that: result is 5 + "sum numbers between 6 and 5". so he asks to clone[5] to return: "sum numbers between 6 and 5" | | | | clone[5] knows that: he can't sum, because 6 is larger than 5. so he returns 0 as result. | | | + clone[4] gets the result from clone[5] (=0) and sums: 5 + 0, returning 5 | | + clone[3] gets the result from clone[4] (=5) and sums: 4 + 5, returning 9 | + clone[2] gets the result from clone[3] (=9) and sums: 3 + 9, returning 12 + clone[1] gets the result from clone[2] (=12) and sums: 2 + 12, returning 14 

and voilá!!

Answer 15

Many of the answers above are very good. A useful technique for solving recursion though, is to spell out first what we want to do and code as a human would solve it . In the above case, we want to sum up a sequence of consecutive integers (using the numbers from above):

 2, 3, 4, 5 //adding these numbers would sum to 14 

Now, note that these lines are confusing (not wrong, but confusing).

 if (a > b) { return 0 } 

Why the test a>b ?, and why return 0

Let's change the code to reflect more closely what a human does

 func sumInts(a: Int, b: Int) -> Int { if (a == b) { return b // When 'a equals b' I'm at the most Right integer, return it } else { return a + sumInts(a: a + 1, b: b) } } 

Can we do it even more human like? 是! Usually we sum up from left to right (2+3+…). But the above recursion is summing from right to left (…+4+5). Change the code to reflect it (The - can be a little intimidating, but not much)

 func sumInts(a: Int, b: Int) -> Int { if (a == b) { return b // When I'm at the most Left integer, return it } else { return sumInts(a: a, b: b - 1) + b } } 

Some may find this function more confusing since we are starting from the 'far' end, but practicing can make it feel natural (and it is another good 'thinking' technique: Trying 'both' sides when solving a recursion). And again, the function reflects what a human (most?) does: Takes the sum of all left integers and adds the 'next' right integer.

Answer 16

I was having hard time to understanding recursion then i found this blog and i already seen this question so i thought i must have to share . You must read this blog i found this extremely helpful it explain with stack and even it explain how two recursion works with stack step by step. I recommend you first understand how stack works which it explain very well here : journey-to-the-stack

then now you will understand how recursion works now take a look of this post : Understand recursion step by step

Its a program :

 def hello(x): if x==1: return "op" else: u=1 e=12 s=hello(x-1) e+=1 print(s) print(x) u+=1 return e hello(3)