程序对自身的调用称递归。
递归的策略就是就是用少量的程序就可描述出解题过程中所需要的多次计算大大的减少了代码数量。
递归能力就是用有限的语句描述无线的集合。
一般来说递归要有边界条件,递归前段和递归后段。当边界条件不满足时,递归前进;当条件满足时就递归返回。
1.例如:用递归求1,2,3,4,5...100的和。
通项公式:Sn=Sn-1+an (n>1)
S0=0;
递归函数这样写:
#include "stdio.h"
int S(int n)
{
printf("/n");
if(n>1) /*界条件不满足时*/
return S(n-1)+n ; /***递归公式****/
else /*界条件满足时** /
return 1; /*界条件就是Sn=1** /
}
void main(void)
{
int num;
num=S(100); /*主函数调用递归函数*/
printf("%d",num);
getch();
}
思路:首先求Sn 再求Sn-1再求Sn-2 ......然而这些Sn Sn-1 Sn-2都是未知的,直到满足临界条件 即n=1时 S1=1(已知量出现)回调已知量 S2=S1+2, S3=S2+3 从而反推回去算出S4 ,S5 ......直到Sn即为所求。
2.典型应用阶乘的算法
n!=(n-1)!*n; (n > 1)
n!=0; (n=1)
用递归求10的阶乘?
程序如下:
#include "stdio.h"
int factorial(int n)
{
if(n>1)
return factorial(n-1)*n; /*算n的阶乘*/
else
return 1;
}
main()
{
int num;
num=factorial(10);
printf("%d",num);
getch();
}
思路: return factorial(n-1)*n; 算出n!
n!是未知的需要算出(n-1)!
................
直到临界状态1!=1 再根据阶乘公式返回去即可算出n!。
一列数的规则如下: 1、1、2、3、5、8、13、21、34...... 求第30位数是多少, 用递归算法实现。
int Foo(int i)
{
if (i <= 0)
return 0;
else if(i > 0 && i <= 2)
return 1;
else return Foo(i -1) + Foo(i - 2);
}