『算法-ACM 竞赛』算法分析设计-递归算法

What’s the 递归算法

定义：
程序直接或间接调用自身的编程技巧称为递归算法（Recursion）。
一个过程或函数在其定义或说明中又直接或间接调用自身的一种方法，它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解，递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量

特点：
任何一个可以用计算机求解的问题所需的计算时间都与其规模 n 有关。问题的规模越小，越容易直接求解，解题所需的计算时间也越少。
分治法的设计思想是，将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。
如果原问题可分割成 k 个子问题（1 ＜ k≤n），且这些子问题都可解，并可利用这些子问题的解求出原问题的解，那么这种分治法就是可行的。
由分治法产生的子问题往往是原问题的较小模式，这就为使用递归技术提供了方便。

注意事项：

1. 递归算法运行效率较低
2. 容易爆栈
3. 一定要设置递归出口不然容易死锁而且爆栈

Why we learn this？

递归是搜索、分治、回溯算法的

例题：

1. Fibonacci 数列

我们之前写过递推的方法，这次我们写递归的方法。
PS：矩阵快速幂和母函数是解决此类问题的最快方式，有兴趣的可以去我博客里看看。

int fib(int n)
{
	if (n<=1) return 1;
	return fib(n-1)+fib(n-2);
}
int main()
{
	int n;
	cin>>n;
	cout<<fib(n)<<endl;
}

2.集合全排列问题

排列组合的普遍复杂度就是 N！

例如 给定 N 求 1-N 的全排列问题
假设 N=3 那么输出 123 132 213 231 312 321

void Perm(int list[], int k, int m)
{
	if(k==m) 	//构成了一次全排列，输出结果
	{
		for(int i=0;i<=m;i++)
			cout<<list[i]<<" ";
		cout<<endl;
	}
	else
		//在数组list中，产生从元素k～m的全排列
		for(int j=k;j<=m;j++)
		{
			swap(list[k],list[j]);
			Perm(list,k+1,m);
			swap(list[k],list[j]);
		}
}
int main()
{
	int n;
	int a[10000];
	cin>>n;
	for(int i=0;i<n;i++)
		cin>>a[i];
	Perm(a,1,n);
}

3.整数划分问题

题目：将一个整数划分为多个整数想加的形式，并输出有所划分方法的数量。
例：6的划分：
6=5+1
6=4+2
6=4+1+1
6=3+3
6=3+2+1
6=3+1+1+1
6=2+2+2
6=2+2+1+1
6=2+1+1+1+1
6=1+1+1+1+1+1

递归转移方程：

实现：

int split(int n,int m)
{
	if(n==1||m==1) return 1;
	else if (n<m) return split(n,n);
	else if(n==m) return split(n,n-1)+1;
	else return split(n,m-1)+split(n-m,m);
}
int main()
{
	int n;
	cin>>n;
	split(n,n);
}

现在增大难度，输出所有的划分方式：

#include <bits/stdc++.h>
using namespace std;
stringstream ss;
int split(int n, int m, string s)
{
    if (m == 0)
    {
        cout << s << endl;
        return 0;
    }
    for (int i = 1; i <= n && i <= m; i++)
    {
        string s1;
        ss.clear();
        ss << i;
        ss>>s1;
        s1= s + (( s[s.size()-1]=='=')? ' ' : '+' )+s1;
        split(i, m - i, s1);
    }
}
int main()
{
    int n;
    cin>>n;
    ss<<n;
    string s<<ss;
    split(n, 10, s+" =");
}

4. 阶乘

递归思想：n! = n * (n-1)! (直接看公式吧)
首先分析数列的递归表达式：

#include <bits/stdc++.h>
using namespace std;
stringstream ss;
int f(int n)
{
    if (n == 1)
        return 1;
    else
        return n * f(n - 1);
}
int main()
{
    int n;
    cin >> n;
    cout << f(n);
}

5.汉诺塔问题

数学描述就是：

有三根杆子 X，Y，Z。X 杆上有 N 个(N>1)穿孔圆盘，盘的尺寸由下到上依次变小。要求按下列规则将所有圆盘移至 Y 杆：

1. 每次只能移动一个圆盘；
2. 大盘不能叠在小盘上面。

递归思想：

1. 将 X 杆上的 n-1 个圆盘都移到空闲的 Z 杆上，并且满足上面的所有条件
2. 将 X 杆上的第 n 个圆盘移到 Y 上
3. 剩下问题就是将 Z 杆上的 n-1 个圆盘移动到 Y 上了

#include <iostream>
#include <cstdio>
using namespace std;

int cnt;

void move(int id, char from, char to)
{
    printf ("step %d: move %d from %c->%c\n", ++cnt, id, from, to);
}

void hanoi(int n, char x, char y, char z)
{
    if (n == 0)
        return;
    hanoi(n - 1, x, z, y);
    move(n, x, z);
    hanoi(n - 1, y, x, z);
}

int main()
{
    int n;
    cnt = 0;
    scanf ("%d", &n);
    hanoi(n, 'A', 'B', 'C');
    return 0;
}

写在最后：
Name:风骨散人，喜欢码代码，码字，目前是一名双非在校大学生，预计考研，热爱编程，热爱技术，喜欢分享，知识无界，希望我的分享可以帮到你！名字的来源：我想有一天我能有能力随心所欲不逾矩，不总是向生活低头，有能力让家人拥有富足的生活而不是为了生计而到处奔波。
文章主要内容：
Python,C++,C 语言,JAVA,C#等语言的教程
ACM 题解、模板、算法等，主要是数据结构，数学和图论
设计模式，数据库，计算机网络，操作系统，计算机组成原理
Python 爬虫、深度学习、机器学习
计算机系408考研的所有专业课内容
一些程序猿常用的软件或者黑科技什么的
目前还在更新中，先关注不迷路。微信公众号，cnblogs（博客园），CSDN 同名“风骨散人”

如果有什么想看的，可以私信我，如果在能力范围内，我会发布相应的博文！
感谢大家的阅读！😘 你的点赞、收藏、关注是对我最大的鼓励！