了解递归函数如何工作 [英] Understanding how recursive functions work
问题描述
了解当面对不知道我们不知道的事情时，我们可能倾向于提出错误的问题或不正确地提出正确的问题，我会分享我的想法我的问题是希望有一个具有相似前景的人可以分享一些知识，以帮助开启递归灯泡！
这里是函数（语法是用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.但我不清楚这个价值是如何实现的。
这些是我的2 hangups：
-
该函数被递归地调用，直到满足条件。那个条件是a> b。当这个条件满足时，返回0.乍一看，我期望返回值为0，这显然是不正确的。
-
打印出'a'在每次迭代中产生一个我期望的值：2,3,4,5（在满足第一条件的a + b> 5 + 1> b的情况下），但是我仍然不知道值达到14。
我的第一个想法是，神奇地发生了类似以下事情：
var answer = a;
answer + = a + 1，直到a> b;
返回答案;
所以排除魔法，我只是没有得到一些东西。我很想了解发生的事情不仅仅是隐含的。
如果有人可以解释这种函数在技术上发生了什么，以及为什么结果不是0以及最终如何
认为混淆源于将其视为多次被称为同一功能。如果你认为它是被调用的同一函数的许多副本，那么它可能会更清晰：
只有函数的一个副本返回0，它是不是第一个（这是最后一个）。因此，调用第一个的结果不是0。
对于第二个混淆，我认为用英语描述递归会更容易一些。阅读此行：
返回a + sumInts（a + 1，b：b）
b条件得到满足。
当您达到a> b条件时，您可能会有一堆（可能任意）的函数副本在正在运行的过程中，所有等待下一个副本的结果，以找出他们应该添加到'a'。
（edit：also，something to请注意，我提到的函数的副本堆栈是一个真实的东西，它会占用真实的内存，并且如果程序太大会导致程序崩溃。编译器可以在某些情况下优化它，但是会耗尽在许多语言中，堆栈空间是递归函数的一个重要和不幸的限制）
As the title explains I have a very fundamental programming question which I have just not been able to grok yet. Filtering out all of the (extremely clever) "In order to understand recursion, you must first understand recursion." replies from various online threads I still am not quite getting it.
Understanding that when faced with not knowing what we don't know, we can tend to ask the wrong questions or ask the right questions incorrectly I will share what I "think" my question is in hopes that someone with a similar outlook can share some bit of knowledge that will help turn on the recursive light bulb for me!
Here is the function (the syntax is written in Swift):
func sumInts(a: Int, b: Int) -> Int {
if (a > b) {
return 0
} else {
return a + sumInts(a: a + 1, b: b)
}
}
We'll use 2 and 5 as our arguments:
println(sumInts(a: 2, b: 5))
Obviously the answer is 14. But I'm not clear on how that value is achieved.
These are my 2 hangups:
The function is called recursively until a condition is met. That condition is a > b. When this condition is met, return 0. At first glance, I would expect the return value to be 0 which is obviously incorrect.
Printing out the value of 'a' on each iteration yields a value which I would expect: 2, 3, 4, 5 (at which point 5+1 > b which meets the first condition: a > b) but I still don't see how the value of 14 is achieved.
My first thought is that something similar to the following is happening magically:
var answer = a;
answer += a+1 until a > b;
return answer;
So ruling out magic, I'm just not getting something. I would love to understand what's happening more than just implicitly.
If someone could kindly explain what technically happens during this kind of function and why the result isn't 0 and how, eventually, a + sumInts(a: a + 1, b: b) = 14, I would be forever in your debt.
解决方案 I think the confusion is stemming from thinking of it as "the same function" being called many times. If you think of it as "many copies of the same function being called", then it may be clearer:
Only one copy of the function ever returns 0, and it's not the first one (it's the last one). So the result of calling the first one is not 0.
For the second bit of confusion, I think it will be easier to spell out the recursion in English. Read this line:
return a + sumInts(a + 1, b: b)
as "return the value of 'a' plus (the return value of another copy of the function, which is the copy's value of 'a' plus (the return value of another copy of the function, which is the second copy's value of 'a' plus (...", with each copy of the function spawning a new copy of itself with a increased by 1, until the a > b condition is met.
By the time you reach the the a > b condition being true, you have a (potentially arbitrarily) long stack of copies of the function all in the middle of being run, all waiting on the result of the next copy to find out what they should add to 'a'.
(edit: also, something to be aware of is that the stack of copies of the function I mention is a real thing that takes up real memory, and will crash your program if it gets too large. The compiler can optimize it out in some cases, but exhausting stack space is a significant and unfortunate limitation of recursive functions in many languages)
这篇关于了解递归函数如何工作的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
