V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
DIJ
V2EX  ›  数学

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

  •  
  •   DIJ · 2015-07-19 17:08:32 +08:00 · 4915 次点击
    这是一个创建于 3400 天前的主题,其中的信息可能已经有所发展或是发生改变。

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

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

    5 条回复    2015-07-24 09:29:22 +08:00
    sandideas
        1
    sandideas  
       2015-07-19 18:03:37 +08:00
    没时间看。。只能说快速幂的原理应该是这样的。
    假如要求3的10次方,等于3的5次方*3的5次方。
    3^5=3^2*3^2*3^1.。。
    递归就是这么走的。
    sandideas
        2
    sandideas  
       2015-07-19 18:11:22 +08:00 via iPhone
    顺便说一下。。不会算到3^0次方。。因为最后有个判断
    jiang42
        3
    jiang42  
       2015-07-19 18:42:01 +08:00
    递归的优点之一就是写出的程序清晰啊。。。
    dorentus
        4
    dorentus  
       2015-07-19 19:35:31 +08:00 via iPhone
    if(x%2!=0) r*=a 被你漏掉了
    vwok
        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);
    按照实际算法思路来就好了
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   3840 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 27ms · UTC 10:16 · PVG 18:16 · LAX 02:16 · JFK 05:16
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.