InkSoul

5.7 KiB

Raw Permalink Blame History

title	date
递归	2022-05-10T09:10:48+08:00

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

阶乘函数

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

 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}

 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

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的划分组成
```
 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
```
 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层调用。
- 递归调用的栈使用情况示意

主算法栈块
M
主算法调用递归算法A的栈块
算法A的第一层递归调用工作记录
算法A的第二层递归调用工作记录
TOP
M

5.7 KiB Raw Permalink Blame History Unescape Escape

5.7 KiB

Raw Permalink Blame History