如何理解递归,如何清晰地利用递归在不背算法模板的条件下写出程序?

2015-07-19 17:08:32 +08:00
 DIJ

我对递归的了解,还仅限在 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 这更加无法理解了......

求各位大神不灵赐教,究竟该如何理解递归,如何清晰地利用递归在不背算法模板的条件下写出程序?

4960 次点击
所在节点    数学
5 条回复
sandideas
2015-07-19 18:03:37 +08:00
没时间看。。只能说快速幂的原理应该是这样的。
假如要求3的10次方,等于3的5次方*3的5次方。
3^5=3^2*3^2*3^1.。。
递归就是这么走的。
sandideas
2015-07-19 18:11:22 +08:00
顺便说一下。。不会算到3^0次方。。因为最后有个判断
jiang42
2015-07-19 18:42:01 +08:00
递归的优点之一就是写出的程序清晰啊。。。
dorentus
2015-07-19 19:35:31 +08:00
if(x%2!=0) r*=a 被你漏掉了
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);
按照实际算法思路来就好了

这是一个专为移动设备优化的页面(即为了让你能够在 Google 搜索结果里秒开这个页面),如果你希望参与 V2EX 社区的讨论,你可以继续到 V2EX 上打开本讨论主题的完整版本。

https://www.v2ex.com/t/206754

V2EX 是创意工作者们的社区,是一个分享自己正在做的有趣事物、交流想法,可以遇见新朋友甚至新机会的地方。

V2EX is a community of developers, designers and creative people.

© 2021 V2EX