递归（一）：递归的基本思想

r囧r小猫 2021-11-24 00:24 540阅读 0赞

递归是算法设计中的一种基本而重要的算法。递归方法通过函数调用自身将问题转化为本质相同但规模较小的子问题，是分治策略的具体体现。

递归算法的定义：如果一个对象的描述中包含它本身，我们就称这个对象是递归的，这种用递归来描述的算法称为递归算法。

先来看看大家熟知的一个的故事： 从前有座山，山上有座庙，庙里有个老和尚在给小和尚讲故事，老和尚讲：从前有座山，山上有座庙，庙里有个老和尚在给小和尚讲故事，老和尚讲：…… 上面的故事本身是递归的，用递归算法描述：

void bonze-tell-story （）

if (讲话被打断)

\{ 故事结束； return； \}

从前有座山，山上有座庙，庙里有个老和尚在给小和尚讲故事；

bonze-tell-story（）；

从上面的递归事例不难看出，递归算法存在的两个必要条件：（1）必须有递归的终止条件，如老和尚的故事一定要在某个时候应该被打断，可以是小和尚听烦了叫老和尚停止，或老和尚本身就只想重复讲10遍等；（2）过程的描述中包含它本身。

递归是一种非常有用的程序设计技术。当一个问题蕴含递归关系且结构比较复杂时，采用递归算法往往比较自然、简洁、容易理解。

递归思想的基本思想是把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解。递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。用递归思想写出的程序往往十分简洁易懂。 一般来说，递归需要有边界条件、递归前进段和递归返回段。当边界条件不满足时，递归前进；当边界条件满足时，递归返回。

使用递归要注意以下几点：

（1）递归就是在过程或函数里调用自身；

（2）在使用递增归策略时，必须有一个明确的递归结束条件，称为递归出口。

**【例1】用递归法计算pn。**  
（1）编程思想。  
1）描述递归关系。  
递归关系是这样的一种关系。设\{U1，U2，U3，…，Un，…\}是一个序列，如果从某一项k开始，Un和它之前的若干项之间存在一种只与n有关的关系，这便称为递归关系。  
当n≥1时，pn=p\*p(n−1)（n=0时，p0=1），这就是一种递归关系。对于特定的pk，它只与k与p(k−1)有关。  
2）确定递归边界。  
在步骤1的递归关系中，对大于k的Un的求解将最终归结为对Uk的求解。这里的Uk称为递归边界（或递归出口）。在本例中，递归边界为k=0，即p0=1。对于任意给定的pn，程序将最终求解到p0。  
确定递归边界十分重要，如果没有确定递归边界，将导致程序无限递归而引起死循环。  
例如以下程序：  
int f(int x)  
\{ return(f(x−1)); \}  
int main()  
\{ cout<<f(5)<<endl; \}  
它没有规定递归边界，运行时将无限循环，会导致错误。  
3）写出递归函数。  
将步骤1）和步骤2）中的递归关系与边界统一起来用数学语言来表示，即  
pn= p\*pn−1 当n>=1时  
pn= 1 当n=0时  
再将这种关系翻译为代码，即一个函数：  
int f(int p , int n)  
\{  
if (n==0) return 1;  
return p\*f(p,n-1);  
\}  
（2）源程序。  
\#include <iostream>  
using namespace std;  
int f(int p , int n)  
\{  
if (n==0) return 1;  
return p\*f(p,n-1);  
\}  
int main()  
\{  
int p, n,k;  
while (cin >>p>>n && p!=0)  
\{  
k=f(p,n);  
cout<<k<<endl;  
\}  
return 0;  
\}

**【例2】分苹果**

把 M 个同样的苹果分放在N 个同样的盘子里，允许有的盘子空着不放，问共有多少种不同的分法？例如，M=7，N=3，则有（7,0,0）、（6,1,0）、（5,2,0）、（5,1,1）、（4,3,0）（4,2,1）、（3,3,1）和（3,2,2）共8种分法。注意：（5，1，1）和（1，5，1）是同一种分法。

（1）编程思路。

所有不同的摆放方法可以分为两类：至少有一个盘子空着和所有盘子都不空。我们可以分别计算这两类摆放方法的数目，然后把它们加起来。

对于至少空着一个盘子的情况，则N 个盘子摆放M 个苹果的摆放方法数目与N-1 个盘子摆放M 个苹果的摆放方法数目相同。对于所有盘子都不空的情况，则N 个盘子摆放M 个苹果的摆放方法数目等于N 个盘子摆放M-N 个苹果的摆放方法数目。我们可以据此来用递归的方法求解这个问题。

设f(m, n) 为m 个苹果，n 个盘子的放法数目，则先对n 作讨论，如果n>m，必定有n-m 个盘子永远空着，去掉它们对摆放苹果方法数目不产生影响；即

if(n>m) f(m,n) = f(m,m)。

当n <= m 时，不同的放法可以分成两类：即有至少一个盘子空着或者所有盘子都有苹果，前一种情况相当于f(m , n) = f(m , n-1); 后一种情况可以从每个盘子中拿掉一个苹果，不影响不同放法的数目，即f(m , n) = f(m-n , n)。总的放苹果的放法数目等于两者的和，即 f(m,n) =f(m,n-1)+f(m-n,n) 。

整个递归过程描述如下：

int f(int m , int n)

if (n ==１|| m == 0) return 1;

if (n > m) return f (m, m);

return f (m , n-1)+f (m-n , n);

递归终止条件说明：当n=１时，所有苹果都必须放在一个盘子里，所以返回１；当没有苹果可放时，定义为１种放法；递归的两条路，第一条n 会逐渐减少，总会到达终止条件 n==1；第二条m 会逐渐减少，因为n>m 时，我们会return f(m , m) ，所以也会到达终止条件 m==0。

（2）源程序

\#include <iostream>

using namespace std;

int f(int m , int n)

if (n==1 || m==0) return 1;

if (n > m) return f (m, m);