面试题:使用递归的方法计算1到100的累加。

2022-06-11 22:53:44

今天去面试，遇到这道题目，有段时间没写程序了，温习一下：

题目是使用递归的方法计算1到100的累加，也就是计算1+2+3+4+........+100。大家想必已经听说过高斯如何计算这道题的故事，也知道答案是5050。我整理了一下使用递归解决的思路，与大家分享。

递归的特点就是递归函数本身会调用自己，对应到逻辑上就是一段逻辑会使用这段逻辑自身。要使用递归的方法解决这道题，就要先用递归的思维方式描叙这道题。

我们来看看如何描叙题目本身，最直观的描叙：“从1开始，后一个数加上前一个数，后一个数是前一个数加一所得，一直加到100”，但这种描叙无法转化为递归的方法。我们试着按递归的思路思考这个问题，“做一件事情的步骤又包含这个事情步骤的自身”：

最开始一定是“1”+“某个值”
如果按老思路，这个“某个值”是“1”再加"1",也就是“2”
到这里，已经完成了一段步骤，并且如果这种思路能形成递归，上面的两步的描叙里面应该会包含对自身同样步骤的一段描叙，但我们仔细想想，里面却没有。
那我们换个角度思考一下，这个“某个值"也可以是‘2’到‘100’累加的和。到这里，我们看到了点希望，因为”累加的和“这个词就是第1、2步在做的事。
那么‘2’到‘100’累加的和又应该是‘2’加上”‘3’到‘100’累加的和“，这里我们已经看到递归的迹象了。
再举一例看看，‘3’到‘100’累加的和又应该是‘3’加上”‘4’到‘100’累加的和“。
对于递归，还有最重要的一点就是这种嵌套何时终止，不然就无穷无尽了。我们看看最后一步，也就是‘100‘到’100‘累加的和是多少？这次我们不用，也无法递归调用了，结果应该直接就是100，所以到这一步，递归终止。