递归算法详解：从概念到实践
递归算法详解：从概念到实践
递归是编程中一个重要的概念，它允许函数在执行过程中调用自身，从而将复杂问题分解为更小的子问题来解决。本文将通过多个具体的编程示例，深入浅出地介绍递归的概念、原理及其在实际编程中的应用。
To Iterate is Human,to Recurse,Divine.(人理解迭代，神理解递归) ——L.Peter Deutsch
递归，在数学与计算机科学中，是指在方法的定义中使用方法自身。也就是说，递归算法是一种直接或间接调用自身方法的算法。其中，直接调用自己称为直接递归，而将a调用b，b又调用a的递归叫做间接递归。
简言之：在定义自身的同时又出现自身的直接或间接调用。
注意：递归必须要有一个退出的条件。
递归的数学模型：数学归纳法
数学归纳法适用于将解决的原问题转化为解决它的子问题，而它的子问题又变成子问题的子问题，而且我们发现这些问题其实都是一个模型，也就是说存在相同的逻辑归纳处理项。当然有一个是例外的，也就是归纳结束的那一个处理方法不适用于我们的归纳处理项，当然也不能适用，否则我们就无穷归纳了。总的来说，归纳法主要包含以下三个关键要素：
- 步进表达式：问题蜕变成子问题的表达式
- 结束条件：什么时候可以不再使用步进表达式
- 直接求解表达式：在结束条件下能够直接计算返回值的表达式
递归三要素：
- 明确递归终止条件(递归出口)；
- 给出递归终止时的处理办法；
- 提取重复的逻辑，缩小问题规模。
说明：递归算法解题通常显得很简洁，但递归算法解题的运行效率较低。而在递归调用的过程当中系统为每一层的返回点、局部量等开辟了栈来存储，递归次数过多容易造成栈溢出等。所以一般不提倡用递归算法设计程序。
引入——斐波那契数列
吼吼，斐波那契数列又被拿来引入啦！
#include<iostream>
using namespace std;
int Fib(int n)
{
if(n==1||n==2)
return 1;
else
return Fib(n-1)+Fib(n-2);
}
int main()
{
int n;
cin>>n;
cout<<Fib(n)<<endl;
return 0;
}
在n>=3时Fib()函数就会自己调用自身
例1.n的阶乘
#include<iostream>
using namespace std;
int fact(int n)
{
if(n==1||n==0)
return 1;
else
return n*fact(n-1);
}
int main()
{
int n;
cin>>n;
cout<<fact(n)<<endl;
return 0;
}
同理。
那么，递归的原理和过程是怎样的呢？
【数据结构与算法】栈中“栈与递归”如下：
函数调用过程
调用前，系统完成：
- 将实参，返回地址等传递给被调用函数
- 为被调用函数的局部变量分配存储区
- 将控制转移到被调用函数的入口
调用后，系统完成：
- 保存被调用函数的计算结果
- 释放被调用函数的数据区
- 依照被调用函数保存的返回地址将控制转移到调用函数
#include<stdio.h>
void fun1(int n){
if(n!=0){
printf("%d\n",n);
fun1(n-1);
}
}
void fun2(int n){
if(n!=0){
fun2(n-1);
printf("%d\n",n);
}
}
int main(){
fun1(6);
printf("\n");
fun2(6);
return 0;
}
我们继续来看例2
例2.前n项和
输入：n
输出：1+2+3+4+5+…+(n-1)+n的和
我们对这道题很熟悉，很容易就能解出来：
#include<iostream>
using namespace std;
int main()
{
int n,sum=0;
cin>>n;
for(int i=1;i<=n;i++){
sum+=i;
}
cout<<sum<<endl;
return 0;
}
那么，用递归的方法求解是怎样的呢？不妨试一试
【参考程序】
#include<iostream>
using namespace std;
int sum(int n){
if(n==1) return 1;
return (sum(n-1)+n);
}
int main()
{
int n;
cin>>n;
cout<<sum(n)<<endl;
return 0;
}
递归的过程（可以把递的过程看做”入栈“，归的过程看做”出栈“）
例3.汉诺塔
题目描述见【数据结构与算法】递推
所以可按"n=2"的移动步骤设计：
- 若n=0，则结束程序，否则继续往下执行
- 用c柱作为协助过渡，将a柱上的n-1片移到b柱上，调用函数mov(n-1,a,b,c);
- 将a柱上剩下的一片直接移到c柱上
- 用a柱作为协助过渡，将b柱上的n-1片移到c柱上，调用函数mov(n-1,b,c,a);
【参考程序】
#include<iostream>
using namespace std;
int k=0,n;
void mov(int n,char a,char c,char b){
//用b柱作为协助过渡，将a柱上的n片移到c柱上
if(n==0) return;//如果n=0，则退出
mov(n-1,a,b,c);//用c柱作为协助过渡，将a柱上的n-1片移到b柱上
k++;
cout<<k<<":from "<<a<<"-->"<<c<<endl;
mov(n-1,b,c,a);//用a柱作为协助过渡，将b柱上的n-1片移到c柱上
}
int main()
{
cin>>n;
mov(n,'a','c','b');
return 0;
}
例4.二分查找
设有n个数已经按从大到小的顺序排列，现在输入x，判断它是否在这n个数中，如果存在则输出"YES"，否则输出"NO"
当n个数排好序时，用二分查找方法速度大大加快。二分查找算法：
- 设有n个数，存放在a数组中，待查找数为x，用L指向数据的高端，用R指向数据的低端，mid指向中间
- 若x=a[mid]，则输出"YES"
- 若x<a[mid]，则到数据后半段查找，R不变，L=mid+1，计算新的mid值，并进行新的一段查找
- 若x>a[mid]，则到数据前半段查找，L不变，R=mid-1，计算新的mid值，并进行新的一段查找
- 若L>R都没有查找到，则输出"NO"
该算法符合递归程序设计的基本规律，可以用递归方法设计。
【参考程序】
#include<iostream>
using namespace std;
int a[101];
void search(int x,int top,int bot){
//二分查找递归过程
int mid;
if(top<=bot){
mid=(top+bot)/2;//求中间数的位置
if(x==a[mid]) cout<<"YES"<<endl;//找到就输出
else{//判断在前半段还是后半段查找
if(x<a[mid]) search(x,mid+1,bot);
else search(x,top,mid-1);
}
}
else cout<<"NO"<<endl;
}
int main()
{
int k,x,L=1,R;
cout<<"输入多少个数？(小于100)"<<endl;
cin>>R;
cout<<"请输入"<<R<<"个数(从大到小)"<<endl;
for(k=1;k<=R;k++){
cin>>a[k];
}
cout<<"请输入要查找的数："<<endl;
cin>>x;
search(x,L,R);
return 0;
}
当你学了STL后，你可以这样写：
#include<iostream>
#include<algorithm>
using namespace std;
int a[101];
int main()
{
int k,x,n;
cout<<"输入多少个数？(小于100)"<<endl;
cin>>n;
cout<<"请输入"<<n<<"个数(从大到小)"<<endl;
for(k=0;k<n;k++){
cin>>a[k];
}
cout<<"请输入要查找的数："<<endl;
cin>>x;
reverse(a,a+n);
if(binary_search(a,a+n,x)) cout<<"YES"<<endl;
else cout<<"NO"<<endl;
return 0;
}
【STL】概述及总结(很全！！！)
例5.集合的划分
【参考程序】
#include<iostream>
using namespace std;
int s(int n,int k){
if((n<k)||(k==0)) return 0;//满足边界条件，退出
if((k==1)||(k==n)) return 1;
return s(n-1,k-1)+k*s(n-1,k);//调用下一层递归
}
int main()
{
int n,k;
cin>>n>>k;
cout<<s(n,k)<<endl;
return 0;
}