【原】算法|1到100求和学算法之无尽的递归

引言

递归作为一种算法在程序设计语言中广泛应用，是指函数/过程/子程序在运行过程序中直接或间接调用自身而产生的重入现像。绝大多数编程语言支持函数的自调用，在这些语言中函数可以通过调用自身来进行递归。

计算理论可以证明递归的作用可以完全取代循环，因此在很多函数编程语言中习惯用递归来实现循环。本系列文章将通过在不利用循环的情况下，如何利用递归算法求解1到100求和问题为例，带领读者一起探索递归的秘密。

问题描述

1到100求和问题几乎是所有编程语言初学者都会接触到的一个问题，其定义如下，编程实现：

1 + 2 + ··· + 100 = ？

限制条件：使用递归算法。

解决方案

所谓递归，就是会在函数的内部逻辑代码中，调用这个函数本身，如何在函数的内部调用呢？想要调用，就要找到函数的等价关系式，这也是递归中递的过程。

以1到100求和这道题为例，可以通过不断地把这个问题分解来不断地缩小(扩大)参数的范围，如把1到100的和这个问题分解为求100的和以及求1到99的和这两个问题。再把1到99的和这个问题分解为求99的和以及求1到98的和这两个问题；把问题分解的公式就是函数的等价公式。若设此题函数名为sum_recursion，等价公式就是sum_recursion(n) = n + sum_recursion(n-1)。

图3. 1求1到5的和问题分解

找到了函数的等价公式就可以在函数内部代码中，调用这个函数本身。但只做到调用函数本身，函数就会一直调用自己形成死循环。因此，必须在函数内部明确递归的结束条件，也就是找到一个出口使函数退出死循环。这个出口一般是明确的，如本题中，sum_recursion(2) = 1 + sum_recursion(1)，在这里sum_recursion(1)就是求1到1的和，这是能明确知道结果为1的。找到出口以后函数就会反推回去计算值，最后返回结果，也就是递归中归的过程。

图3. 2求1到5的和问题反推计算值

代码示例：

def sum_recursion(n):     # 递归出口      if n == 1:          return 1     # 函数的等价关系式分解问题      else:          return n + sum_recursion(n-1) print(sum_recursion(100))

结语

本文介绍了使用递归算法如何求解1到100求和问题，通过找到函数的等价关系式、递归出口就可以快速完成求解。

本文算法完成了使用递归算法对1到100求和问题的求解，但是存在哪些问题呢？欢迎下方留言讨论。

实习编辑：欧洋

责编 ：雀跃

能力越强，责任越大。

实事求是，严谨细致。

---

微信号：算法与编程之美