C++ 递归函数详细解析——C++日常学习随笔

1. 递归函数

1.1 递归函数的定义

递归函数：即在函数体中出现调用自身的函数，即函数Func(Type a,……)直接或间接调用函数本身；
递归函数：在数学上，关于递归函数的定义如下：对于某一函数f(x)，其定义域是集合A，那么若对于A集合中的某一个值x0，其函数值f(x0)由f(f(x0))决定，那么就称f(x)为递归函数；
递归函数：不能定义为内联函数；

1.2 递归的本质

递归函数的例子：

(1)例子一：等差数列

数列1 3 5 7 9……代码实现输入一个数n，输出数列第n项的值。

#include<iostream>
using namespace std;
int f(int n)
{
    if(n==1)
        return 1;
    else
        return f(n-1)+2;
}
int main()
{
    int n;
    cin >> n;
    cout << f(n);
    return 0;
}

解释：递归关系：f(n-1)+2,递归出口：1；

(2)例子二：阶乘n!

递归的数学函数描述：
f(n)=1 (n=1)
f(n)=n*f(n-1) (n>1)

递归的C++函数描述：
int f(nt n)
{
    if(n==1) 
        return 1;
    return n*f(n-1);
}

注：由于f(13)>2^32。所以对于int型(无符号类型)的表示范围，其n的取值范围只有1<=n<=12了。

(3)例子3：Fibonacci数列

斐波那契数列：1，1，2，3，5，8，13，21，34，55，89…

递归的数学函数描述：
f(n)=0 (n=0)
f(n)=1 (n=1)
f(n)=f(n-1)+f(n-2) (n>2)

递归的C++函数描述：
int f(int n)
{
    if((n==0) || (n==1))
        return n;
    return f(n-1)+f(n-2) ;
}

#include<iostream>
using namespace std;
int f(int n)
{
    if(n==1||n==2)
        return 1;
    else
        return f(n-1)+f(n-2);
}
int main()
{
    int n;
    cin>>n;
    cout<<f(n);
    return 0;
}

(4)例子4：王小刀切饼：

王小二自夸刀工不错，有人放一张大的煎饼在砧板上，问他:“饼不许离开贴板，切n(1<=n<=100)刀最多能分成几块?

输入格式：输入切的刀数n

输出格式：输出切n刀最多切的块数

#include<iostream>
using namespace std;
int f(int n)
{
    if(n==1)
        return 2;
    else
        return f(n-1)+n;
}
int main()
{
    int n;
    cin>>n;
    cout<<f(n);
    return 0;
}

解释：递归关系：f(n-1)+n,递归出口：n=1；

先列举几项就会发现规律

第一刀2

第二刀2+2=4

第三刀 4+3=7

第四刀 7+4=11

……

第n-1刀 i

第n刀 i+n

如图

(5)例子5：杨辉三角

#include<iostream>
using namespace std;
int f(int x,int y)
{
    if(y==0||x==y)
        return 1;
    else
        return f(x-1,y-1)+f(x-1,y);
}
int main()
{
    int x,y;
    cin>>x>>y;
    cout<<f(x,y);
    return 0;
}

(6)例子6：最大公约数

#include<iostream>
using namespace std;
int gcd(int a,int b)
{
    int r=a%b;
    if(r==0) return b;
    return gcd(b,r);
}
int main()
{
    int m,n;
    cin>>m>>n;
    cout<<gcd(m,n);
    return 0;
}

解释：

辗转相除法又名欧几里得算法，目的是求出两个正整数的最大公约数。它是最古老的算法，其可追溯刀公元前300年前。

这条算法基于一个定理：两个正整数a和b（a>b)，他们的最大公约数等于a除以b的余数c和较小数b之间的最大公约数。

递归有直接递归和间接递归之分：

直接递归：直接调用函数本身；
间接递归：指函数体中没有直接调用自身函数，而是调用了另一个函数，在那个函数里，出现了调用本函数的语句。或者，在那个函数里，又调用了一个其他函数，反复出现调用其它函数，而最后有一个函数调用了本函数；
注：递归函数在运行中，其调用与被调用函数的指令代码是同一个函数副本，只不过各个不同运行中的调用点作为状态的一部分，在栈中被分别保护了起来。因此，是C++的函数机制决定了递归操作中的数据独立性，因而使递归调用成为可能。