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

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

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