【算法】算法设计与分析 课程笔记 第二章 递归与分治策略

2.1 递归

直接或间接地调用自身的算法称为递归算法。

用函数自身给出定义的函数称为递归函数。

2.1.1 阶乘

首先得想到一个求阶乘的函数：

这个函数的下面那个式子就用到了调用自身，所以可以用递归来实现，将主问题拆分成若干层的子问题，最底层的一定是当 n=0 时，阶乘的值，由此可以设计以下程序：

#include<bits/stdc++.h>
using namespace std;
int jiecheng(int n){if(n==0)return 1;//最底层必然返回1elsereturn n*jiecheng(n-1);//不是最底层，那就继续向下求阶乘
}
int main(){int n;cin>>n;cout<<jiecheng(n);return 0;
}

2.1.2 汉诺塔问题

三座塔上，所有圆盘从下到上按照由大到小的顺序拍好在A塔上，现在要求将所有圆盘原封不动地移到B盘上，并且大盘不能放在小盘上。

现在拆解问题，要把n个圆盘从A移到B，可以先把上面的 n-1 个移到C，再将剩下的那个移到B，最后将C上的 n-1 个移到B。