Processing math: 5%
NOIP学习小站
西安交通大学附属中学航天学校

递归函数

函数体中可以调用其它函数,如果一个函数题中又调用了自己,这样的函数称为递归函数。显然,函数体中不应该是无条件的递归调用,否则就和“死循环”一样的效果了。也就是在满足某些条件的时候不递归调用自身,这也就是递归函数的“出口”。

一、计算阶乘

对于阶乘,n! = 1 \times 2 \times ... \times (n-1) \times n(n-1)! = 1 \times 2 \times ... \times (n-1) ,可知:

\begin{equation} n!=\left\{ \begin{aligned} 1\quad(n=1) \\ n \times (n-1)! \quad(n>1)\end{aligned} \right. \end{equation}

如果用f(n)表示n!,可知:

\begin{equation} f(n)=\left\{ \begin{aligned} 1\quad(n=1) \\ n \times f(n-1) \quad(n>1)\end{aligned} \right. \end{equation}

如果用自定义函数int f(int n);来计算并返回n!的值,那么在函数体里可以使用n*f(n-1)来作为计算结果,可见函数int f(int n);中又调用了自己,这就是递归函数:

Plain text
Copy to clipboard
Open code in new window
EnlighterJS 3 Syntax Highlighter
#include<iostream>
using namespace std;
int f(int n){
if(n==1) return 1; //递归出口
return n*f(n-1); //递归调用自身
}
int main()
{
for(int i=1;i<=10;i++){
cout<<f(i)<<endl;
}
return 0;
}
#include<iostream> using namespace std; int f(int n){ if(n==1) return 1; //递归出口 return n*f(n-1); //递归调用自身 } int main() { for(int i=1;i<=10;i++){ cout<<f(i)<<endl; } return 0; }
#include<iostream>
using namespace std;
int f(int n){
	if(n==1) return 1;	//递归出口 
	return n*f(n-1);	  //递归调用自身 
}
int main()
{
	for(int i=1;i<=10;i++){
		cout<<f(i)<<endl;
	}
    return 0;
}

以main函数中i=3时,调用f(3)为例,整个调用过程如下:

从上面分析可知,递归函数有点类似于“剥洋葱”,一层套着一层,要向下一直“剥”到最里层(也就是递归出口),然后还有向上逐层返回的过程。

二、逆序输出

再来看一个问题,输入n个整数,然后逆序输出所有的整数,我们知道在输入一个整数后需要将这个整数保存下来(当然要保存所有整数需要用到数组),等所有整数都输入完毕了,才能逆序输出:

Plain text
Copy to clipboard
Open code in new window
EnlighterJS 3 Syntax Highlighter
#include<iostream>
using namespace std;
int a[1011];
int main(){
int n;
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=n;i>=1;i--) cout<<a[i]<<" ";
return 0;
}
#include<iostream> using namespace std; int a[1011]; int main(){ int n; cin>>n; for(int i=1;i<=n;i++) cin>>a[i]; for(int i=n;i>=1;i--) cout<<a[i]<<" "; return 0; }
#include<iostream>
using namespace std;
int a[1011]; 
int main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=n;i>=1;i--) cout<<a[i]<<" ";
    return 0;
}

其实也可以使用递归函数来实现,大家可以自行分析下面参考程序递归函数的执行过程:

Plain text
Copy to clipboard
Open code in new window
EnlighterJS 3 Syntax Highlighter
#include<iostream>
using namespace std;
int n; //n是全局变量
//处理第k个数:输入并输出
void f(int k){
if(k==n+1) return; //递归出口
int m;
cin>>m;
f(k+1); //递归调用,处理第n+1个数
cout<<m<<" ";
}
int main(){
cin>>n;
f(1);
return 0;
}
#include<iostream> using namespace std; int n; //n是全局变量 //处理第k个数:输入并输出 void f(int k){ if(k==n+1) return; //递归出口 int m; cin>>m; f(k+1); //递归调用,处理第n+1个数 cout<<m<<" "; } int main(){ cin>>n; f(1); return 0; }
#include<iostream>
using namespace std;
int n;		//n是全局变量 
//处理第k个数:输入并输出
void f(int k){
    if(k==n+1) return;	//递归出口
    int m;
    cin>>m;
    f(k+1);		//递归调用,处理第n+1个数
    cout<<m<<" ";
}
int main(){
    cin>>n;
    f(1);
    return 0;
}
Plain text
Copy to clipboard
Open code in new window
EnlighterJS 3 Syntax Highlighter
#include<iostream>
using namespace std;
//输入并输出
void f(int k){
if(k==0) return; //递归出口
int m;
cin>>m;
f(k-1); //递归调用
cout<<m<<" ";
}
int main(){
int n;
cin>>n;
f(n);
return 0;
}
#include<iostream> using namespace std; //输入并输出 void f(int k){ if(k==0) return; //递归出口 int m; cin>>m; f(k-1); //递归调用 cout<<m<<" "; } int main(){ int n; cin>>n; f(n); return 0; }
#include<iostream>
using namespace std;
//输入并输出
void f(int k){
	if(k==0) return;  //递归出口
	int m;
	cin>>m;
	f(k-1);		//递归调用
	cout<<m<<" ";
}
int main(){
    int n;
    cin>>n;
    f(n);
    return 0;
}

三、斐波那契数列

前面介绍的斐波那契数列的第nfib(n)的计算公式是:

\begin{equation} fib(n)=\left\{ \begin{aligned} 1\quad(n \le 2) \\ fib(n-1)+fib(n-2) \quad(n \ge 3)\end{aligned} \right. \end{equation}

和上面的计算阶乘一样,可以使用递归函数处理,参考程序如下:

Plain text
Copy to clipboard
Open code in new window
EnlighterJS 3 Syntax Highlighter
#include<iostream>
using namespace std;
long long fib(int n){
if(n<=2) return 1; //递归出口
return fib(n-1)+fib(n-2); //递归调用自身(2次)
}
int main()
{
cout<<fib(20)<<endl;
return 0;
}
#include<iostream> using namespace std; long long fib(int n){ if(n<=2) return 1; //递归出口 return fib(n-1)+fib(n-2); //递归调用自身(2次) } int main() { cout<<fib(20)<<endl; return 0; }
#include<iostream>
using namespace std;
long long fib(int n){
	if(n<=2) return 1;			//递归出口 
	return fib(n-1)+fib(n-2);	 //递归调用自身(2次) 
}
int main()
{
	cout<<fib(20)<<endl;
    return 0;
}

如果调用fib(40),会发现耗时已经接近1s了,如果调用fib(50),耗时远远超过1s(实际测试在普通配置PC上耗时40s左右),这是什么原因呢?我们修改一下代码:

Plain text
Copy to clipboard
Open code in new window
EnlighterJS 3 Syntax Highlighter
#include<iostream>
using namespace std;
long long fib(int n){
cout<<"fib("<<n<<")"<<endl; //通过输出额外信息来测试函数调用过程
if(n<=2) return 1; //递归出口
return fib(n-1)+fib(n-2); //递归调用自身
}
int main()
{
cout<<fib(6)<<endl;
return 0;
}
#include<iostream> using namespace std; long long fib(int n){ cout<<"fib("<<n<<")"<<endl; //通过输出额外信息来测试函数调用过程 if(n<=2) return 1; //递归出口 return fib(n-1)+fib(n-2); //递归调用自身 } int main() { cout<<fib(6)<<endl; return 0; }
#include<iostream>
using namespace std;
long long fib(int n){
	cout<<"fib("<<n<<")"<<endl;	//通过输出额外信息来测试函数调用过程 
	if(n<=2) return 1;			 //递归出口 
	return fib(n-1)+fib(n-2);	  //递归调用自身 
}
int main()
{
	cout<<fib(6)<<endl;
    return 0;
}

在fib函数里添加上语句cout<<"fib("<<n<<")"<<endl;,那么每调用一次fib函数,就会输出fib函数“调用”信息。程序输出结果如下:

Plain text
Copy to clipboard
Open code in new window
EnlighterJS 3 Syntax Highlighter
fib(6)
fib(5)
fib(4)
fib(3)
fib(2)
fib(1)
fib(2)
fib(3)
fib(2)
fib(1)
fib(4)
fib(3)
fib(2)
fib(1)
fib(2)
8
fib(6) fib(5) fib(4) fib(3) fib(2) fib(1) fib(2) fib(3) fib(2) fib(1) fib(4) fib(3) fib(2) fib(1) fib(2) 8
fib(6)
fib(5)
fib(4)
fib(3)
fib(2)
fib(1)
fib(2)
fib(3)
fib(2)
fib(1)
fib(4)
fib(3)
fib(2)
fib(1)
fib(2)
8
fib(6)调用过程

可知调用fib(6),一共调用了2次fib(4)、3次fib(3)、5次fib(2)、3次fib(1),其实这些调用一次就已经计算出结果了,这里出现了不必要的重复调用的情况。如果调用fib(50),仅fib(20)就被重复调用多达1346269次,fib(4)更是被调用了2971215073次(接近30亿次)。这么多不必要的重复调用导致程序效率低下。

那么如何提高程序的运行效率呢?可以用一个全局数组a来记录计算结果,在函数体中,将fib(n)的结果保存到a[n]中,在计算前判断a[n]的值不为0的话可以直接返回a[n](已经计算过):

Plain text
Copy to clipboard
Open code in new window
EnlighterJS 3 Syntax Highlighter
#include<iostream>
using namespace std;
long long a[51]; //全局数组用来记录fib数列每项
long long fib(int n){
if(a[n]) return a[n]; //已经计算过,直接返回
if(n<=2) return a[n] = 1;
return a[n] = fib(n-1)+fib(n-2);
}
int main()
{
cout<<fib(50)<<endl;
return 0;
}
#include<iostream> using namespace std; long long a[51]; //全局数组用来记录fib数列每项 long long fib(int n){ if(a[n]) return a[n]; //已经计算过,直接返回 if(n<=2) return a[n] = 1; return a[n] = fib(n-1)+fib(n-2); } int main() { cout<<fib(50)<<endl; return 0; }
#include<iostream>
using namespace std;
long long a[51];  //全局数组用来记录fib数列每项 
long long fib(int n){
	if(a[n]) return a[n]; //已经计算过,直接返回 
	if(n<=2) return a[n] = 1;
	return a[n] = fib(n-1)+fib(n-2); 
}
int main()
{
	cout<<fib(50)<<endl;
    return 0;
}

四、辗转相除法求最大公约数

再来看辗转相除法求最大公约数,前面已经介绍了该算法的思路:

  1. 输入m和n
  2. r←m%n,若r==0,输出n,算法结束。
  3. 互换:执行赋值,m←n,n←r,并返回第2步。

可以使用do...while循环求解问题:

Plain text
Copy to clipboard
Open code in new window
EnlighterJS 3 Syntax Highlighter
#include<iostream>
using namespace std;
int main()
{
int m,n,r;
cin>>m>>n;
do{
r = m%n;
m = n;
n = r;
}while(r!=0);
cout<<m; //注意这里是输出m
return 0;
}
#include<iostream> using namespace std; int main() { int m,n,r; cin>>m>>n; do{ r = m%n; m = n; n = r; }while(r!=0); cout<<m; //注意这里是输出m return 0; }
#include<iostream>
using namespace std;
int main()
{
    int m,n,r;
    cin>>m>>n;    
    do{
        r = m%n;
        m = n;
        n = r;
    }while(r!=0);
    cout<<m;   //注意这里是输出m 
    return 0;
} 

分析上面的第 3 步,其实就是计算 n 和 r(也就是 m%n)的最大公约数。可以用递归函数实现:

\begin{equation} gcd(m,n)=\left\{ \begin{aligned} n\quad(m\%n=0) \\ gcd(n,m\%n) \quad(m\%n \neq 0)\end{aligned} \right. \end{equation}

还可以简化为:

\begin{equation} gcd(m,n)=\left\{ \begin{aligned} m\quad(n=0) \\ gcd(n,m\%n) \quad(n>1)\end{aligned} \right. \end{equation}

Plain text
Copy to clipboard
Open code in new window
EnlighterJS 3 Syntax Highlighter
#include<iostream>
using namespace std;
int gcd(int m,int n){
return m%n==0?n:gcd(n,m%n);
}
int main()
{
int x,y;
cin>>x>>y;
cout<<gcd(x,y)<<endl;
return 0;
}
#include<iostream> using namespace std; int gcd(int m,int n){ return m%n==0?n:gcd(n,m%n); } int main() { int x,y; cin>>x>>y; cout<<gcd(x,y)<<endl; return 0; }
#include<iostream>
using namespace std;
int gcd(int m,int n){
	return m%n==0?n:gcd(n,m%n);
}
int main()
{
    int x,y;
    cin>>x>>y;
    cout<<gcd(x,y)<<endl;
    return 0;
}
Plain text
Copy to clipboard
Open code in new window
EnlighterJS 3 Syntax Highlighter
#include<iostream>
using namespace std;
int gcd(int m,int n){
return n==0?m:gcd(n,m%n);
}
int main()
{
int x,y;
cin>>x>>y;
cout<<gcd(x,y)<<endl;
return 0;
}
#include<iostream> using namespace std; int gcd(int m,int n){ return n==0?m:gcd(n,m%n); } int main() { int x,y; cin>>x>>y; cout<<gcd(x,y)<<endl; return 0; }
#include<iostream>
using namespace std;
int gcd(int m,int n){
	return n==0?m:gcd(n,m%n);
}
int main()
{
    int x,y;
    cin>>x>>y;
    cout<<gcd(x,y)<<endl;
    return 0;
}

求最大公约数还有辗转相减法:

\begin{equation} gcd(m,n)=\left\{ \begin{aligned} m\quad(m=n) \\ gcd(n,m) \quad(m<n)\\ gcd(n,m-n) \quad(m>n)\end{aligned} \right. \end{equation}

还可以对辗转相减法改良,用来高效计算高精度数(后面会介绍)的最大公约数:

思考问题

1.输入正整数m,n(m\leq3,n\leq5),计算Ackmann函数的结果:

\begin{equation} akm(m,n)=\left\{ \begin{aligned} n+1\quad(m=0) \\ akm(m-1,1) \quad(m>0且n=0) \\ akm(m-1,akm(m,n-1)) \quad(m>0且n>0)\end{aligned} \right. \end{equation}

2.n条两两相交的直线将平面划分成多少个区域?注意没有任何超过2条直线相交于同一点的情况。

3.楼梯有n级台阶,上楼可以一步上一级台阶,也可以一步上两级台阶。编一程序,计算共有多少种不同的走法。

登录

注册