递归的数学思维
递归是一种数学上分而自治的思维
递归须要有边界条件
当边界条件不满足时,递归持续进行
当边界条件满足时,递归进行
递归函数
函数体外部能够调用本人
递归函数
函数体中存在自我调用的函数
递归函数是递归的数学思维在程序设计中的利用
递归函数必须有递归进口
函数的有限递归将导致程序栈溢出而解体
递归函数设计示例一
用递归的办法编写函数求字符串长度
“D.T.software”
strlen(s) = 1 + strlen(s + 1) *s != ‘0’
strlen(s) = 0 *s == ‘0’
例子 47-1:
#include "stdio.h"
int strlen_r(char *s)
{if(*s != '\0')
{return 1 + strlen_r(s+1);
}
else
{return 0;}
}
int main()
{printf("%d\n",strlen_r("abc"));
printf("%d\n",strlen_r(""));
return 0;
}
输入后果:
3
0
递归函数设计示例二
斐波拉契数列递归解法
-1,1,2,3,5,8,13,21,…
数学公式:
fac(n) = fac(n-1) + fac(n-2) n>=3;
fac(n) = 1 n==2;
fac(n) = 1 n==1;
例子 47-2:
#include "stdio.h"
int fac(int n)
{if(n == 1)
{return 1;}
else if(n == 2)
{return 1;}
else if(n >= 3)
{return fac(n - 1) + fac(n - 2);
}
}
int main()
{printf("%d\n",fac(1));
printf("%d\n",fac(2));
printf("%d\n",fac(5));
return 0;
}
输入后果:
1
1
5