什么是递归？具体来讲就是把规模大的问题转化为规模小的相似的子问题来解决。在函数实现时，因为解决大问题的方法和解决小问题的方法往往是同一个方法，所以就产生了函数调用它自身的情况。
比如怎么求n的阶（n*(n-1)*(n-2)*.....*1）我只需要知道结束条件到1时结束，那么这个时候我可以定义结束条件为n==1，此时如果我要求n的阶，我是不是可以分解为n*（n-1的阶)？
以此类推，n-1的阶是不是等于求n-1*（n-2）的阶？
现在我求3的阶，假设我定义的函数为fun(int n);
我传值为3，fun(3)；
把3的阶分为3*2的阶层，把2的阶分为2*1的阶。
过程就由fun(3)=3*fun(2),fun(2)=2*fun(1);
fun(1)（n==1时）返回1变成
fun(1)=1，fun(2)=2*1，fun3=3*fun(2)=3*2*1;就解决了问题。
图片来自慕课网
代码就是:
#include
int fun(int n)
{
if(n==1) return 1;
return n*fun(n-1);
}
int main()
{
int i;
scanf("%d",&i);
printf("%d",fun(i));
return 0;
}
首先总结递归的特点：
（1）可以把一个旧问题分开变成一个新问题，且新问题与原问题有着相同的形式,例如fun(n)=n* fun(n-1)；
(2)有可以结束的出口，就是必须要有个结束的条件.
递归的优势：代码更简洁清晰,可读性更好。
递归的缺点：电脑需要使用内存去记住你调用了多少个递归函数，需要耗费大量的运行空间。
给出几个经典例题：
Fibonacci数列用递归实现：
代码：
#include
int fun(int n)
{
if(n==1||n==2) return 1;
return fun(n-1)+fun(n-2);
}
int main()
{
int i;
scanf("%d",&i);
printf("%d",fun(i));
return 0;
}
递归实现汉诺塔：
图片来自博客园
代码：
#include
int fun(int n)
{
if(n==1) return 1;
return 1+2*fun(n-1);
}
int main()
{
int i;
scanf("%d",&i);
printf("%d",fun(i));
return 0;
}
分析:
汉诺塔，假设有n块木板。
那么我得先把n-1快木板的位置移动到第三根柱子上
然后我在移动第n块木板到第二根柱子上
然后再把第三根珠子上的n-1块木板移动到第二根柱子上。
于是return 1+2*fun(n-1).你也可以写成fun(n-1)+1+fun(n-1)
注意找到”出口“，出口就是n=1时，只需要移动一次.
---------------------------------------------------------------------
想了解更多，可以关注公众号＂程序员快速修炼＂
网友评论