所有的计算都是递归；要理解递归首先要理解递归。
艾舍尔版画《手》
程序设计思想之一“递归”历来是同学们的理解难点。据说，**要理解递归首先要理解递归! **当然，我们有更简单的理解方法。比如，我们思考一个简单的问题：给一个正整数n，求1+2+3+...+n的值。
重复强调以下算法设计原则：
1、明确输入：正整数n；
2、明确计算目标：1到n之间整数的累加；
3、设计处理过程。
当然，这么难的计算，我们还不知道如何处理！即使我们不知道如何处理，大概也应该能写出这样的一个尚不知道处理流程的sum0函数：
int sum0(int n){
计算累加并赋值给res；
return res；
}
如果sum0是一个懒惰的家伙，他抗议说：嘿，我可不是高斯，我怎么会算这样的东西？太难了！我只知道如果n==1的累加和，就等于1！但是，如果你告诉我n-1之间整数的累和的答案res，我倒是可以可以告诉你答案是：n+res! 这家伙真是天才。
于是我们只好去请另外一个家伙来算是n-1之间的累和，比如我找到的是sum1，给他一个整数n-1 。不可思议的是，sum1也同样抗议，嘿，你帮我算出(N-1)-1之间整数的累和吧......于是我只好再去找sum2来做接下来的工作。这样的把戏持续下去值得有一个天才的输入是1。如下所示：
sum0(5) ----> sum1(4) ----> sum2(3) ----> sum3(2) ----> sum4(1) ---->1
如果我们要算的数是n==5，sum4接到任务的时候，输入是5 - 4 == 1，他刚开口想说，嘿，太难了，我......但是他只好闭嘴，因为求1到1之间数的累加就是1。好吧，sum4无奈地又没好气地对sum3说，答案是1。这时候sum3也没办法偷懒了，因为他必须承担自己的工作，告诉sum2答案，3。如此不断地返回，如下所示：
15<---- sum0(5) <--10-- sum1(4) <--6-- sum2(3) <--3-- sum3(2) <--1-- sum4(1)
值得注意的是，这一群懒惰的家伙都一个德行而没有任何差别：告诉我n-1为输入的累和答案，我就告诉你n为输入的累和答案。所以，作为雇主的话，也许我只需要雇佣一群sum0来干这项工作。因为sum0与sum1(或其他任何一个sum)的处理过程没有任何区别。于是工作流程就变成了：
sum0(5) ----> sum0(4) ----> sum0(3) ----> sum0(2) ----> sum0(1) ---->1
15<---- sum0(5) <--10-- sum0(4) <--6-- sum0(3) <--3-- sum0(2) <--1-- sum0(1)
既然所有的sum都一样，我们只需要定义一个新的函数sum，如下：
int sum(int n){
if(n == 1)
return 1;
return sum(n-1) + n；//递归的返回点！
}
以上讲的都是设计思想，没有涉及具体递归程序在计算机中的实现。以下描述递归在计算机中的实现，与教科书不同，为了帮助理解我们牺牲了一定的严谨性与准确性。看完我这里的描述，希望大家还是要阅读课本。
如果把sum程序编译成机器可执行的代码，我们一定会得到一个指令集，记为sum。sum(n)表示接受输入为n的那段程序，当他执行到程序最后一句，它要调用自己“本身”，大家难理解的是所谓“本身”是什么。其实没什么神秘的，如果我们用一种不怎么正确的理解方式，可以想象sum正常地去拷贝一份sum代码出来放到内存的某个地方，给它输入值n-1，然后等待sum(n-1)给它返回答案。这里的关键点是，把程序递归地调用自己看为对多个自己的代码拷贝的调用。
还有一个关键点是，sum(n-1)必须在返回值给sum(n)，这里称为递归的返回点。为何一定会返回？注意，sum程序一开始就设定了递归结束的条件：n == 1 。每一次调用sum，n的值都要减1，根据Well-order principle(不懂就忽略，这里只是告诉你有这个东西)，必然会在某个时刻使得n到达1，然后sum(1)把值返回给调用它的sum(2)。准确定义递归结束条件是写递归程序首先需要考虑的问题。
注意，return这个关键词可不是只是返回一个值这么简单。程序应该如何在内存中驻留，程序该如何执行，如何返回（return干了啥）等，这些都不不是本文的内容。请参看相关课本内容。
扩展一小步，把求n的累加变成求n-1的累加，也可以直观地把这种思路理解为，当我们要解一个大的问题，我们可以把问题分解成小问题，然后根据小问题的答案来整合出整个大问题的答案。试试做以下思考：
作业：
1、求n阶乘：等于求n-1的阶乘，再乘上n；
2、二分查找：把数据分为两部分，根据条件在某一部分进行检索；
3、归并排序：对n个数值进行排序等同于对两次n/2数值的排序的归并；
4、GCD：求A和B的最大公因子，等于求更小数值B与A % B的GCD；
从解决问题的角度，递归的思想就是一种解决问题的方法，被广泛地应用在程序设计中。说到严谨的递归理论，其实，在高校不传已久咯，《计算理论导引》有此方面的严格理论描述。
2017年7月整理
网友评论