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

This topic created in 3942 days ago, the information mentioned may be changed or developed.

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

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

endl

cout

used

5 replies • 2015-07-24 09:29:22 +08:00