了解递归函数的工作原理 [英] Understanding how recursive functions work
问题描述
正如标题所解释的那样，我有一个非常基本的编程问题，但我还无法理解.过滤掉所有(非常聪明的)为了理解递归，你必须首先理解递归".来自各种在线线程的回复我仍然不太明白.
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!
这是函数(语法是用 Swift 编写的):
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)
}
}
我们将使用 2 和 5 作为我们的参数:
We'll use 2 and 5 as our arguments:
println(sumInts(a: 2, b: 5))
显然答案是 14.但我不清楚这个价值是如何实现的.
Obviously the answer is 14. But I'm not clear on how that value is achieved.
这是我的两个挂断:
递归调用函数，直到满足条件.该条件是 a > b.当这个条件满足时，返回0.乍一看，我希望返回值是0，这显然是不正确的.
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.
在每次迭代中打印出 'a' 的值会产生一个我期望的值:2, 3, 4, 5(此时 5+1 > b 满足第一个条件:a > b) 但我仍然没有看到 14 的值是如何实现的.
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.
如果有人能解释一下这种函数在技术上发生了什么，为什么结果不是 0 以及最终如何 a + sumInts(a: a + 1, b: b) = 14，我将永远欠你的债.
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:
该函数只有一个副本返回 0，而且它不是第一个(它是最后一个).所以调用第一个的结果不是0.
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 "返回'a'的值加(函数的另一个副本的返回值，即'a'的副本的值(函数的另一个副本的返回值，即第二个副本的返回值)'a' 的值加 (..."，函数的每个副本都会产生一个自身的新副本，并增加 1，直到满足 a > 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.
当你达到 a > b 条件为真时，你有一个(可能是任意的)很长的函数副本堆栈，所有副本都在运行中，所有副本都在等待下一个副本的结果找到找出他们应该添加到a"中的内容.
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屋！
