151 lines
5.7 KiB
Markdown
151 lines
5.7 KiB
Markdown
---
|
||
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 |
|