俗话说“”迭代是人，递归是神“”
那递归神在什么地方？
简单地说，递归是函数内的层层循环找结果
引用一下专业术语：
在计算机编程里，递归指的是一个过程：函数不断引用自身，直到引用的对象已知。
使用递归解决问题，思路清晰，代码少。但是在主流高级语言中（如C语言、Pascal语言等）使用递归算法要耗用更多的栈空间，所以在堆栈尺寸受限制时（如嵌入式系统或者内核态编程），应避免采用。所有的递归算法都可以改写成与之等价的非递归算法。
递归在程序编程多次用到
简单的弄一个求阶乘的递归算法吧：
一个数的阶乘就是这个数连乘每个比前一个数小1的数，例如5的阶乘是：5 * 4 * 3 * 2 * 1, 0和1的阶乘是1.用公式实现：
fac(n) = 1 n=1 ,n=0
n * fac(n - 1) n > 1
#include "stdafx.h"
int fac(int n)
{
if (n == 0 || n == 1)
return 1;
return n*fac(n - 1);
}
int _tmain(int argc, _TCHAR* argv[])
{
printf("%d ", fac(3));
printf("%d ", fac(5));
printf("%d ", fac(7));
return 0;
}
分别求出3,5,7的阶乘
3！=6，5！=120,7！=5040
这还只是简单的递归阶乘算法，但却看出它的神奇所在吧！
接下来就要领会下用递归做的斐波那契数列吧
来看看基本定义：
斐波那契数列指的是这样一个数列 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233，377，610，987，1597，2584，4181，6765，10946，17711，28657，46368[1]
斐波那契数列特别指出：第0项是0，第1项是第一个1。
这个数列从第3项开始，每一项都等于前两项之和。
斐波那契数列的发明者，是意大利数学家列昂纳多·斐波那契（Leonardo Fibonacci），生于公元1170年，卒于1250年，籍贯是比萨。他被人称作“比萨的列昂纳多”。1202年，他撰写了《算盘全书》（Liber Abacci）一书。他是第一个研究了印度和阿拉伯数学理论的欧洲人。他的父亲被比萨的一家商业团体聘任为外交领事，派驻地点相当于今日的阿尔及利亚地区，列昂纳多因此得以在一个阿拉伯老师的指导下研究数学。他还曾在埃及、叙利亚、希腊、西西里和普罗旺斯等地研究数学。
递推公式
斐波那契数列：1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, …
如果设F(n）为该数列的第n项（n∈N+）。那么这句话可以写成如下形式：
显然这是一个线性递推数列
写个程序了解一下吧
int fib(int n)
{
if (n == 0)
return 0;
if (n == 1)
return 1;
return fib(n - 1) + fib(n - 2);
}
int _tmain(int argc, _TCHAR* argv[])
{
printf("%d ", fib(3));
printf("%d ", fib(5));
printf("%d ", fib(7));
return 0;
}
当n==1是为1，当n==0为0,fib(2)=fib(1)+fib(0)=1+0等于1fib(3)=fib(2)+fib(1)=2,，同理fib(5)和fib(7)分别是5和13
除此之外斐波那契数列还有许多表示方法，下面就再列举两个吧。
方法一：利用公式每次计算出2个斐波那契数列值，直接输出。由于每次输出2个数，所以循环20次可输出40个数。
#define N 40
int main(void)
{
int f1=1,f2=1;
int i;
for(i=1; i<=N/2; i++ )
{
printf("%15d%15d", f1, f2);
if(i%2==0)
printf(" ");
f1 += f2;
f2 += f1;
}
return 0;
}
方法二：利用数组计算并保存前40个斐波那契数列的数（不输出第0项），然后循环40次输出数组元素。
分析：根据斐波那契数列的特征，利用数组可计算数列的前40个数为：
fib[0]= fib[1]=1，
fib[2]= fib[1]+ fib[0]，…
从第3个数开始可以用下式计算：
fib[n]= fib[n-1]+fib[n-2] (2≤n≤39)
源程序：
#include
#define N 40
int main(void)
{
int i;
int fib[N]={1,1};
for(i=2;i
fib[i]=fib[i-1]+fib[i-2];
for(i=0;i
{
if(i%4==0) printf(" ");
printf("%15d",fib[i]);
}
return 0;
}
除此之外递归的应用还有很多种，远不止这一些。。。。。
玩玩其他操作
int fac(int n)
{
for (int i = 0; i < n; i++)
printf(" ");
printf("factorial: %d ", n);
if (n == 0)
{
printf("returning : 1 ");
return 1;
}
else
{
int result = n*fac(n - 1);
for (int i = 0; i < n; i++)
printf(" ");
printf("returning: %d ", result);
return result;
}
}
int main()
{
fac(5);
getchar();
return 0;
}
网友评论