递归算法典型特征及经典递归例子代码实现
递归(recursion):程序调用自身的编程技巧。
递归满足2个条件:
1)有反复执行的过程(调用自身)
2)有跳出反复执行过程的条件(递归出口)
递归算法的通用解法:
-
f(para……){
-
if(…)//终止条件
-
{…//递归的终止项,一般是最低项
-
}
-
else{//继续递归
-
…//譬如for循环,遍历所有可能路径
-
…//某些递归逻辑,注意回退事件
-
}
递归算法的典型例子:
(1)阶乘
n! = n * (n-1) * (n-2) * …* 1(n>0)
-
<pre name=“code” class=“html”>//阶乘
-
int recursive(int i)
-
{
-
int sum = 0;
-
if (0 == i)
-
return (1);
-
else
-
sum = i * recursive(i-1);
-
return sum;
-
}
(2)汉诺塔
-
void hanoi(int n,int p1,int p2,int p3)
-
{
-
if(1==n)
-
cout<<“盘子从”<<p1<<“移到”<<p3<<endl;
-
else
-
{
-
hanoi(n-1,p1,p3,p2);
-
cout<<“盘子从”<<p1<<“移到”<<p3<<endl;
-
hanoi(n-1,p2,p1,p3);
-
}
-
}
(3)全排列
第二位之后的数,依次和第一位交换··· 依次做第一,剩下的全排序
如1,2,3三个元素的全排列为:
1,2,3
1,3,2
2,1,3
2,3,1
3,1,2
3,2,1
-
void Perm(int list[],int k,int m)
-
{
-
if (k == m-1)
-
{
-
for(int i=0;i<m;i++)
-
{
-
printf(“%d”,list[i]);
-
}
-
printf(“n”);
-
}
-
else
-
{
-
for(int i=k;i<m;i++)
-
{
-
Swap(list[k],list[i]);
-
Perm(list,k+1,m);
-
Swap(list[k],list[i]);
-
}
-
}
-
}
(4)斐波那契数列
斐波纳契数列,又称黄金分割数列,指的是这样一个数列:1、1、2、3、5、8、13、21、……
这个数列从第三项开始,每一项都等于前两项之和。
-
long Fib(int n)
-
{
-
if (n == 0)
-
return 0;
-
if (n == 1)
-
return 1;
-
if (n > 1)
-
return Fib(n-1) + Fib(n-2);
-
}
(5)八皇后
-
void Backtrack(int k,int cnt)
-
{//回溯算法主程序
-
-
if(k < 0 || cnt == n)//棋牌摆放完毕 or 以摆满n后
-
{
-
if(cnt == n)
-
{
-
printf(“No.%d:\n”,++total);
-
for(int i = 0; i < n; i++)
-
{
-
for(int j = 0; j < n; j++)
-
printf(” %c “,Chess[i][j]);
-
putchar(\’\n\’);
-
}
-
putchar(\’\n\’);
-
}
-
}
-
else
-
{
-
int r = k / n, c = k % n;
-
if(Judge(r,c))
-
{//可放置一皇后
-
Chess[r][c] = queen;
-
Backtrack(k-1,cnt+1);
-
Chess[r][c] = blank;//不行的话就要回退重置
-
}
-
Backtrack(k-1,cnt);
-
}
-
-
}
(6)选择题
1、排列组合解法:
从A到Z可以理解为:
横向的距离为4个单元
纵向的单元为2个单元
这个理解的基础上,这个问题就转化为排列组合问题了。
求最短路径条数,其实就是把这个横向的4个单元和纵向的2个单元进行组合就行了。
所以,从A到Z的最短路径条数为C(6,2)=15
但是题目给出的是右上角和左下角各自缺了一块,所以要减掉2种情况。
所以,最后的最后,结果是C(6,2)-2=13.
从A到Z可以理解为:
横向的距离为4个单元
纵向的单元为2个单元
这个理解的基础上,这个问题就转化为排列组合问题了。
求最短路径条数,其实就是把这个横向的4个单元和纵向的2个单元进行组合就行了。
所以,从A到Z的最短路径条数为C(6,2)=15
但是题目给出的是右上角和左下角各自缺了一块,所以要减掉2种情况。
所以,最后的最后,结果是C(6,2)-2=13.
2、递归式解法
(7)最大公约数之辗转相除法
版权声明:本文为gzhnan原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。