我对递归的了解,还仅限在 return fib(n-1)+fib(n-2);
的程度,以下是两个最近碰到不能够理解的程序,第一个是快速幂:
int quickpower(int a,int x)
{
if (x==0) return 1;
int r=quickpower(a,x/2);
r=r*r;
cout <<x<<endl;
if(x%2!=0) r*=a;
return r;
}
例如 a=3, x=3 时:
r=quickpower(3,1)
quickpower(3,1)=quickpower(3,0)*quickpower(3,0)=1
......
r=1
或者其他任何样例,似乎按照这个思路运算下来都是 1 ,请问这个用大脑模拟程序运算的思路是哪里错了?
又如求全排列:
void full_permutation(int depth)
{
if(depth==n+1)
{
for(int i=1;i<=n;i++)
cout <<item[i]<<" ";
cout <<endl<<endl;
return ;
}
for(int j=1;j<=n;j++)
if(used[j]==0)
{
used[j]=1;
item[depth]=j;
//cout <<"depth="<<depth<<endl;
//cout <<"used["<<j<<"]="<<used[j]<<endl;
full_permutation(depth+1);
used[j]=0;
}
}
depth=1
used[1]=1
depth=2
used[2]=1
depth=3
used[3]=1
1 2 3
depth=2
used[3]=1
depth=3
used[2]=1
1 3 2
depth=1
used[2]=1
depth=2
used[1]=1
depth=3
used[3]=1
2 1 3
......
321
以上是 n=3 时输出的部分结果(注释代码)。
第一次循环输出 1 2 3 没有问题, return 后,我输出结果(注释代码)看到 depth=2, j=3 , j=3 我倒还能理解,最后循环到 4 ,上一个状态下 j=3 , depth 为何是 2 呢,返回上一个状态 depth 不该是 3 么?难道说返回了两次,如果是这样第二次返回又是从哪里进入的呢?
再向下,输出 2 1 3 的这一次,进入时 depth=1 , j=2 这更加无法理解了......
求各位大神不灵赐教,究竟该如何理解递归,如何清晰地利用递归在不背算法模板的条件下写出程序?
1
sandideas 2015-07-19 18:03:37 +08:00
没时间看。。只能说快速幂的原理应该是这样的。
假如要求3的10次方,等于3的5次方*3的5次方。 3^5=3^2*3^2*3^1.。。 递归就是这么走的。 |
2
sandideas 2015-07-19 18:11:22 +08:00 via iPhone
顺便说一下。。不会算到3^0次方。。因为最后有个判断
|
3
jiang42 2015-07-19 18:42:01 +08:00
递归的优点之一就是写出的程序清晰啊。。。
|
4
dorentus 2015-07-19 19:35:31 +08:00 via iPhone
if(x%2!=0) r*=a 被你漏掉了
|
5
vwok 2015-07-24 09:29:22 +08:00
if (x==0) return 1;
int r=quickpower(a,x/2)*quickpower(a,x-x/2); 按照实际算法思路来就好了 |