InkSoul/content/algorithm/递归.md

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

---

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

---------------------

* 阶乘函数
  * 可递归地定义为$n!= \begin{cases}1,& \text{n=0} \\\\ n(n-1)!,&\text{n>0} \end{cases}$
  
     ```java
      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}$
    
     ```java
      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$
  
     ```java
    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$的划分组成
    
    
     ```java
      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
    
     ```java
      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               |