本文来自“天狼啸幽月”的投稿，已获独家授权
关于设计递归函数，个人有一点总结和心得，和大家分享一下。
从一个简单的例子开始
#include "stdio.h"
int fun(int n) //求1+2+3+…+n的结果
{
if(n==1)
return 1;
return n+fun(n-1);
}
int main( void )
{
printf("10及以内的自然数之和是%d", fun(10) );
return 0;
}
运行结果是：
我们注意到，函数fun里面调用了一个函数fun，也就是调用了自己，
这种函数调用自己的技巧我们就称为递归算法
，而这个调用了自己的函数fun就是一个
递归函数
。
函数fun的运行过程是这样的：
大家在设计递归函数时，可能也会像上图这样去思考每一层的变化，这样一来往往让人头大。
其实，
根本不用这样，设计递归函数其实很简单，基本上只考虑它的第一层就可以了
，设计它甚至比设计普通的函数还要简单，因为它有便利之处（后面会讲到）。
但是，要做到这样，还需要一些理解上的技巧，我会详细给大家讲明。
为了说明方便，函数fun和它调用的fun我们要分开称呼，外层的fun称作1号fun，被1号调用的fun就称为2号fun，如果调用了多个fun，就3号、4号这样顺延；而如果遇到要按上面的递归结构说明更深层的fun的情况，取名也这样顺延。
回头来解析本例，如何写出这个递归函数。
1. 首先我们要想，函数fun应该设计成一个怎样的功能？这是最重要的一环。
主要看需求，满足需求的情况下微调即可。
比如我们的需求是求n以内的自然数之和，那么我们就这样设计fun的功能——给予正整数n，返回n及以内的自然数之和。
函数功能设计（决定）好之后，那么要得到10以内的自然数之和也就很简单了，所以main里通过fun( 10 ) 就能得到答案了。
2. 制定了功能后，接着就要实现功能了。
作为递归函数，需要调用自己，
调用时只需当它是一个普通函数就行，
因为它的参数、返回值、功能等都已明确，不用去想它还没实现这件事，普通函数怎么用它就怎么用。
但是，有个小问题，按这个思路，fun最简单的实现应该是这样：
int fun(int n)
{
return fun( n );
}
毕竟根据fun的功能，直接调用fun( n ) 就能得到结果了，然后将结果返回不就实现本函数了吗？
哈哈，这样会死循环，刚刚的方法还不够，需要加点限制——在“当做一个普通函数来用”这个思路的基础上，加上“
不能原封不动地把自己的参数给它
”。
比如fun首先会收到10，那么它调用2号fun时，就不能给它10，至少要改变一点。
同样的，如果1号fun收到的是a、b、c，那么调用2号fun时就不能给a、b、c，稍微改变一点，比如给a-1、b、c。
受到这条限制后，最简单的实现方法就变成了：
int fun(int n)
{
return n+fun( n-1 );
}
这个方法也就是让自己只计算最简单的一部分，剩下的任务全交给2号去做。
当然，根据这个理论，实现的方法太多了，这样也是可以的
int fun(int n)
{
return n + n-1 + fun( n-2 );
}
这仍然是“自己只计算一点点，剩下的全交给2号去做”的思路，只是比起上一个，这次1号计算的稍微多了一点而已。
3. 想办法结束递归。
递归也是一种循环，循环语句尚且有结束循环的条件，递归当然也应该有。
不过需要注意的是，
这个结束的条件需要放在调用2号之前
，因为如果不这样做的话，仍然是无休止递归，控制流始终无法到达结束条件这里。
那么，如何写结束条件呢？可以分两种情况来考虑，一种是按最简的方法实现的，此时基本考虑最简单的情况即可；当实现不是最简时，情况要考虑多点。
最简的实现方法如下：
int fun(int n)
{
return n+fun( n-1 );
}
那么此时最简单的情况就是n为1，结束条件就这样写：
int fun(int n)
{
if( n==1 )
return 1;
return n+fun( n-1 );
}
当然，你可能觉得最简单的情况是n为0，这也可以（不过根据需求，最简情况理应是1）：
int fun(int n)
{
if( n==0 )
return 0;
return n+fun( n-1 );
}
下面是没按最简方式来实现的方案：
int fun(int n)
{
return n + n-1 + fun( n-2 );
}
这时再用n==1（或n==0）来作为结束条件就有漏洞了，比如当n为2时，传给2号fun的是0，n无法经过1，死循环。
此时的方法稍复杂点——
根据收到的参数与给2号的参数的差来考虑结束条件
（简单来说就是让1号和2号的参数衔接，不要出现断层）
以及从递归结构的尾端的角度来验证正确性
（简单来说就是去测试几个边缘值看会不会死循环）。
概括就是
根据参数设条件
，以及
验证
。
比如fun收到的是n，传给2号的是n-2，中间少了n-1，那么1号fun就应该考虑n和n-1两种最简的情况，比如我们可以认为n为1或0时最简：
int fun(int n)
{
if( n==1 || n==0 )
return n;
return n + n-1 + fun( n-2 );
}
也可以认为n为1和2时最简：
int fun(int n)
{
if( n==1 )
return 1;
if( n==2 )
return 2+1;
return n + n-1 + fun( n-2 );
}
接下来是验证环节，测试几个值看看会不会有缺漏，不然又会是死循环。
假如n为5（取值随意，不放心就稍微取宽泛点），则2号得到n=3，3号得到n=1，3号收到的1遇到结束条件而正确返回。
假如n为4，则2号得到n=2，会遇到结束条件而正确返回。
假如n为3，则2号得到n=1，会遇到结束条件而正确返回。
假如n为2，遇到结束条件而正确返回。
假如n为1，遇到结束条件而正确返回。
只要调用时不乱来
，那么目前就验证完毕。
而如果担心n的参数为0或负数等错误情况，另加一个结束条件即可：
int fun(int n)
{
if( n<=0 ) //考虑的错误情况
return 0; //这里要看你设计在错误情况下返回什么值了
if( n==1 )
return 1;
if( n==2 )
return 2+1;
return n + n-1 + fun( n-2 );
}
至此，基本方法已经说明完毕，我们做个归纳总结：
1. 设定好函数的功能（包括参数和返回值的设计），这是最关键的一环。
2. 将自身作为一个普通函数来调用，认定它能完成它的工作。
3. 调用自身时给的参数不能和自己的完全相同。
4. 将一个最简单的情况作为结束条件，放在调用自身之前。
5. 检查结束条件是否有疏漏。
如果对这个过程和理论还不能理解，可以借助这个小故事：
main想要用fun来求n以内的自然数之和，但函数fun就想，诶呀好麻烦呀，赶紧应付应付得了，搞完回家喝喝小酒才是生活呀，该怎么应付呢，诶，有了，我知道有个叫fun的函数，它可以计算n以内的自然数之和，让它来搞就好了嘿嘿嘿，诶，等等，它的名字怎么这么眼熟呢，唉，不管了，就让它帮我计算1～10的和好了，诶呀，突然才想起，主上大人给我制定过一条规则——“调用它时给的参数不能和自己的完全相同”，上有政策，下有对策，main给我10，既然规定我不能把10给fun的话，那我就给9，把它的计算结果再加个10就可以交差了，嘻嘻嘻，聪明如我。
fun完成了工作正回家呢，突然眼前景色一闪，它回到了工作的地方并收到通知——计算1～9的和。是不是喝酒喝太多眼花了，不管了，先把工作完成再说。它故技重施，偷懒用2号计算1～8的和，自己把结果再加上9交差。
fun又回家了，然后它又突然回到了工作的地方，fun开始觉得不对劲了，工作的时候努力回想前因后果，它终于想起，它使唤的函数fun不正是自己吗？原来让自己回来工作的，就是过去的自己！
既然发现了问题就要想办法阻止，可是自己偷懒惯了，未来的自己也不是现在的自己，干脆还是像以前一样交给未来的自己干吧，不过为了防止自己永无止境地干下去，必须要设一个结束条件。
既然计算的是1～n的和，那么n最后就是1，让最后计算1的自己不要再偷懒使唤别的函数就可以了。结束条件写哪里呢？这时fun又想起了主上大人制定的规则——“结束条件要放在调用自身前”，不愧是传说中的主上大人，原来他已经知晓一切，fun在心里对主上肃然起敬。
学习了方法后，接下来我们通过两个例子来验证成果——汉诺塔、反转链表。
汉诺塔问题
汉诺塔是一个游戏，游戏规则如下：
如图有A、B、C三根柱子，A柱子上有一些叠起来的圆盘，大的在下，小的在上，现在要把圆盘都转移到C柱上，移动规则是：
1. 每次移动一个圆盘到另一根柱子上；
2. 大的盘子不能在小的上面。
（这种游戏网上很多，可以先试玩看看）
题目是：指定A柱子上的圆盘数，移动到C柱子上，程序应显示圆盘在柱子间的移动过程。
老规矩
一：设计函数功能。
题目要求把n个圆盘从A柱子移到C柱子，那我们就把函数的功能设计为——把n个圆盘从某根柱子移动到另一根柱子上并显示移动过程。
函数原型设为void hanoi( int n, char a, char b, char c )
a表示初始情况圆盘所在的柱子
c表示要转移的柱子
b表示用来中转的柱子
n表示a柱子上的圆盘数
三个char变量存储的是三根柱子的名字。
函数功能设计好后，那么main要得到从’A’柱移动10个圆盘到’C’柱的过程，只需一行即可—— hanoi ( 10 , ‘A’ , ‘B’ , ‘C’ )
二：实现函数功能
依照hanoi的功能，可以让它移动n-1个盘子，自己则移动剩下的一个，于是我们只需三步即可完成这个过程：
第一步，让2号hanoi移动n-1个圆盘到B柱子。
由于对1号来说，a是自己的起始柱，b是中转柱，c是目标柱，因此它要让2号把盘子从a移动到b，所以调用hanoi( n-1 , a , c , b ) ，也就是对2号来说，1号的b柱就是它的目标柱。效果如下：
第二步，1号将一个圆盘从A盘移动到C盘。
由于实际上并没有什么盘子的数据，因此输出移动过程就是在移动盘子了——printf(“%c—>%c\n”, a, c) ，它表示将起始a柱的一个圆盘移动到目标c柱：
第三步，2号将b柱上n-1个圆盘移动到c柱上——调用hanoi( n-1 , b, a, c ) ，结果如下：
三. 结束条件：
当圆盘数为1就是最简情况
if(n==1)
{
printf("%c--->%c\n",a, c); //转移一个圆盘直接从起始柱转到目标柱
return ; //必须要返回才能结束
}
得出代码：
#include "stdio.h"
//(圆盘数量，起始柱，中转柱，目标柱)
void hanoi(int n, char a, char b, char c)
{
if(n==1)
{
printf("%c--->%c\n",a, c);
return ;
}
hanoi(n-1, a, c, b);
printf("%c--->%c\n", a, c);
hanoi(n-1, b, a, c);
}
int main( void )
{
hanoi(3, 'A', 'B', 'C'); return 0;
}
四. 检查：
由于n==1是结束条件，而n在调用时都是按1递减，因此当n大于1时，n最终都会变成1而结束，不考虑n为负数或0这种错误的情况，已正确实现。
对此方法的思考
你们可能会觉得荒诞—— 2号能让n-1个圆盘直接转移？难道可以无视“一次移动一个”和“大的在上小的在下”这些规则？何等荒谬！怎么做到的？
这正是此方法的魅力，也正是前面说的“更便利”的所在。
如果不按递归来写，那会很复杂，而按这种思路的递归来写，直接凭空得到了一个大帮手——一个叫hanoi的函数，它能完成n个盘子的转移，简直就像配备了一个完美的API，它总是能刚好满足我们的需求，要不是有一个规则限制（调用时不能给出一样的参数），任务甚至简单到直接调用它就完成了，而即便有这个限制，也不过是让我们实现最简单的一层，其余更复杂的事务全交给这个“API”去完成了，还有比这更完美和简单的事吗？
这也难怪大家会觉得不可思议、无法理解，毕竟天底下哪有这样的好事，但它确实实现了，那么我们也不得不承认——递归算法是何等高明和美妙！
但有个问题还是要解释的——为什么这么简单无脑的方法真的可以实现？
前面说过，递归也是一种循环，循环就是重复，说明不同层的递归函数仍然是高度相似的，它们都是在完成一个相同的任务，也就是说，这个任务我们只要实现一次就行了，就像循环语句里的循环体，而我们也确实把这个单次的任务的实现写出来了，也就是2号做的事务之外，由我们实现的那最简单的一层。
所以，
“调用时不能给出完全相同的参数”这个规则，除了防止无限递归外，也是在让你去实现一个基本的步骤
，而递归的实现，不过就是在不断循环这个步骤罢了。
这个方法基本上可以适应绝大多数递归算法，不过，有些情况可能需要稍稍注意，设计递归函数时，我们总是需要各种参数，但是第一次调用时（比如main对该函数的调用）却不一定喜欢给这些参数，比如汉诺塔，目前为止几乎所有的汉诺塔游戏都是从A柱转移到C柱，这几乎是默认的，那么调用时只需给出盘子数才是最简洁方便的设计，但递归函数的参数显然不能这么设计，不然没法递归了，对于这种情况，我们可以将对递归函数的调用包装一次，就像这样：
void view_hanoi( int n )
{
hanoi( n , 'A' , 'B' , 'C' );
}
int main( void )
{
view_hanoi( 3 ); return 0;
}
反转链表
本次我们改变顺序，先展示代码，然后解读代码：
#include "stdio.h"
#include "stdlib.h"
struct node
{
int data; //链表数据
struct node * next; //指向下一个结点的指针
};
//用递归创建链表，参数为链表的结点数,返回头结点
struct node* create( int num )
{
if( num<=0 )
return NULL;
struct node* p = malloc( sizeof(struct node) );
p->data = num;
//剩下的结点用create递归创建
p->next = create( num-1 );
return p;
}
//反转头结点为p的链表并返回新的头结点
struct node* reverse( struct node* p )
{
if( p==NULL )
return NULL;
//如果没有后继结点，那么p就是链表头
if( p->next == NULL)
return p;
//将p->next开头的链表反转
struct node* head = reverse( p->next );
//将p插入链表尾（反转后p->next是链表尾）
p->next->next = p;
//p成为链表尾后，p->next应为NULL
p->next = NULL;
//返回以head开头，p结尾的链表的头结点
return head;
}
//递归版的链表释放，功能设计为：释放p所指的链表
void my_free( struct node* p )
{
if( p==NULL )
return;
my_free( p->next );
free( p );
}
int main (void)
{
struct node *p , * head = create(10);
printf("反转之前：");
for( p=head ; p!=NULL ; p=p->next )
printf("%d ", p->data );
head = reverse( head );
printf("\n反转之后：");
for( p=head ; p!=NULL ; p=p->next )
printf("%d ", p->data );
my_free( head );
return 0;
}
本例使用了3个递归函数——
递归创建链表
、
递归释放链表
、
递归反转链表
，接下来分别解析。
递归创建链表——create函数
struct node* create( int num )
{
if( num<=0 )
return NULL;
struct node* p = malloc( sizeof(struct node) );
p->data = num;
p->next = create( num-1 );
return p;
}
功能：指定生成的结点数量（给予参数），返回头结点的地址。
实现：先创建了一个结点作为头结点并设置数据后，用2号创建num-1个结点的链表，返回它第一个结点的地址给头结点的next指针，于是创建完毕，返回头结点p的地址。
结束条件：考虑到参数是递减1传递，那么肯定会经过0，于是当num==0时返回NULL，考虑到错误情况，因此设置结束条件num<=0。
递归释放链表——my_free函数
void my_free( struct node* p )
{
if( p==NULL )
return;
my_free( p->next );
free( p );
}
功能：给予头结点的地址，释放该链表。
实现：先调用2号释放从第二个结点开始的链表，也就是把除头结点外剩下的结点释放了，然后释放头结点。
结束条件：链表逐点传递，会经过链表尾，设尾端NULL为结束条件。
需要注意的是，这个过程不能反过来，比如像这样：
free( p );
my_free( p->next );
如果p释放了，p->next的值也就没有了，这不是递归和本方法的问题，站在普通调用的角度来看也是这个情况。当然，如果你硬要这样做也有办法：
struct node* t = p->next;
free( p );
my_free( t );
递归反转链表——reverse函数
struct node* reverse( struct node* p )
{
if( p==NULL )
return NULL;
if( p->next == NULL)
return p;
struct node* head = reverse( p->next );
p->next->next = p;
p->next = NULL;
return head;
}
功能：给予头结点的地址，反转链表，返回新的头结点的地址。
实现：先调用2号，让它把第二个结点开始的链表反转，得到反转后链表的头结点head，然后将原本的头结点p放到链表尾端，返回头结点的地址head。
这个过程略有点绕，我们用图来说明，首先是原链表的样子：
先将p结点之后的链表（也就是从结点9开始的链表）反转，头结点也就变为了1（创建head来保存头结点地址），而由于结点p没有变化，因此p的下一个结点依然是9：
由于结点p的问题，整个链表还没完全反转，因此再做几个操作——让结点9的next指向p（即p成为结尾），p的next指向NULL：
如此，链表反转完毕，返回head。
结束条件：当结点只有一个时是最简情况（p==NULL是排除错误情况），判断是否只有一个结点的方法是看它的next指针是否为NULL。
从另一方面来看，实现的方法中，p->next->next必须保证p->next不为空，即至少是在有两个结点的情况下进行的反转，因此结束条件设为1个。
这个思路的一个难点就是要想清楚如何把头结点p放到链表的结尾，你可以从头结点遍历，但其实完全没必要，既然是反转的话，第二个结点就会成为倒数第二个结点，p的内容一直没变过，所以可以直接找到结点9，两次赋值操作就能让它成为尾结点。
结语
关于递归的例子就讲解到这里吧。
如果面对的是较长的递归函数，也无需惊慌，按照我们设定的步骤操作就行了
首先将函数功能明确，以快速排序和归并排序为例，虽然都需要递归，但排序的算法不一样，这个时候设计函数功能就需要包含具体的排序方式，如果在设计功能时仅说明是排序的话，那么实现时就无从下手，因为用递归实现排序的方法有很多种；
接着根据设计的功能去实现，利用自己（2号），实现一遍单层的逻辑，如果代码较长，说明你可能没有实现最简方案，或者它确实比较复杂，以至于实现单层就需要较多代码，比如tree命令的实现。
往期精彩回顾