递归

• 直接或间接地调用自身的算法称为递归算法
• 用函数自身给出定义的函数称为递归函数
• 每个递归函数都必须有非递归定义的初始值，否则递归函数无法计算

• 可递归地定义为$n!= \begin{cases}1,& \text{n=0} \\ n(n-1)!,&\text{n>0} \end{cases}$

  1 2 3 4 5

  public static int Factorial(int n){ if(n==0) return 1; return n*Factorial(n-1); }

Fibonacci数列

• 可递归地定义为$F(n)=\begin{cases}1, &\text{n=0},1 \\ F(n-1)+F(n-2) &\text{n>1} \end{cases}$

1
2
3
4
5

 public static int fibonacci(int n){ 
 if(n<=1)
       return 1;  
 return fibonacci(n-1)+fibonacci(n-2);   
 }

排列问题

• 当$n=1时，perm(R)=(r)$,其中r是集合R中唯一的元素；

• $当n>1时,perm(R)=(r)$ $perm(R)由(r_1)perm(R_1),(r_2)perm(R_2),\cdots,(r_n)perm(R_n)构成$

• 算法perm(list,k,m)递归地产生所有前缀是list[0:k-1],且后缀是list[k:m]的全排列的所有排列。调用perm(list,0,n-1)即产生list[0:n-1]的全排列

• 一般情况下，$k<m$

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

  public static void perm(Object[] list,int k,int m){ if(k==m){ //只剩一个元素 for(int i=0;i<=m;i++) System.out.print(list[i]); System.out.println(); } else //还有多个元素，递归产生排列 for(int i=k;i<=m;i++) { MyMath.swap(list,k,i); perm(list,k+1,m); MyMath.swap(list,k,i); } } public static class MyMath{ public static void swap(Object[] list,int k,int m){ int temp = k; k = m; m = temp; } }

整数划分问题

• 将正整数$n$表示成一系列正整数之和，$n=n_1+n_2+...+n_k$,其中$n_1\geq n_2\geq ...\geq n_k\geq 1,k\geq 1$

• 将最大加数$n_1$不大于$m$的划分个数记作$q(n,m)$可建立如下递归关系

  • 当最大加数$n_1$不大于1时，任何正整数n只有一种划分形式，即$n=\begin{matrix} n \\ \overbrace{1+1+\cdots+1}\end{matrix}$
  • 最大加数$n_1$实际上不能大于$n$。因此，$q(1,m)=1$。
  • 正整数$n$的划分由$n_1=n$的划分和$n_1\leq n-1$的划分组成
  • 正整数$n$的最大加数$n_1$不大于$m$的划分由$n_1=m$的划分和$n_1\leq m-1$的划分组成

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

 public static int q(int n,int m){
         if((n<1)||(m<1))
             return 0;
         if((n==1)||(m==1))
             return 1;
         if(n<m)
             return q(n,n);
         if(n==m)
             return q(n,m-1)+1;
         return q(n,m-1)+q(n-m,m);
     }

Hanoi塔问题

• 设a,b,c是三个塔座。开始是在塔座a上有一叠共n个圆盘，这些圆盘自下而上，由大到小地叠在一起。各圆盘从小到大编号为1，2，···，n。现要求将塔座a上的这一叠圆盘移到塔座b上，并仍按同样顺序叠置。在移动圆盘时应该遵守以下移动规则。

  • 每次只移动一个圆盘
  • 任何时刻都不允许将较大的圆盘压在较小的圆盘之上。
  • 在满足前两个规则的前提下，可将圆盘移至a，b，c任一塔座上

• 递归关系

  • $n=1$时，将编号为一的圆盘从塔座a直接移至塔座b上即可。
  • $n>1$时，需要利用塔座c作为辅助塔座，
    • 将$n-1$个较小的圆盘依照移动规则从塔座a移至塔座c，
    • 将剩下的最大圆盘从塔座a移至塔座b，
    • 将$n-1$个较小的圆盘依照移动规则从塔座c移至塔座b

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

 public static void hanoi(int n,char a,char b,char c){
         if(n>0){
             hanoi(n-1, a, c, b);
             move(n,a,b);
             hanoi(n-1,c,b,a);
         }

 }
 public static void move(int n,char a,char b){
         System.out.println("第"+n+"个盘子从"+a+"--->"+b);
     }

递归调用总结和系统原理

• 实现递归调用的关键：为算法建立递归调用工作栈
• 运行被调用算法前的行为
  • 为所有实参指针，返回地址等信息传递给被调用算法
  • 为被调用算法的局部变量分配存储区
  • 将控制转移到被调用算法的入口
• 从被调用算法返回调用算法时
  • 保存被调用算法的计算结果
  • 释放分配给被调用算法的数据区
  • 依照被调用算法保存的返回地址将控制转移到调用算法
• 嵌套调用时的系统原则：后调用先返回，即算法间的信息传递和控制转移通过栈来实现
• 递归算法的调用层次
  • 调用一个递归算法的主算法为第0层算法
  • 从主算法调用递归算法为进入第1层调用
  • 从第i层递归调用本算法为进入第i+1层调用。
  • 退出第i层递归调用，则返回至i-1层调用。
• 递归调用的栈使用情况示意