C++递归函数的用法（附带实例）

所谓递归函数，就是函数自己调用自己。从定义中可以看出，函数递归调用是函数嵌套调用的一种特殊形式。

设计递归函数解决问题的优点是，问题描述清楚，代码可读性强，结构清晰，代码量比使用非递归方法少。缺点是递归程序的运行效率较低，无论是从时间角度还是从空间角度都比非递归程序差。对时间复杂度和空间复杂度要求较高的程序，使用递归函数调用时要慎重。

递归函数必须定义一个停止条件，否则函数将永远递归下去。

【实例 1】利用递归函数求解 n 的阶乘。阶乘的计算公式为：n! =1×2×3×…×n。以 n 等于 4 为例：

4! 等于 4*3!；
3! 等于 3*2!；
2! 等于 2*1!；
1! 等于 1。

当计算 4! 时，只要知道 3!；计算 3! 时，只要知道 2！，以此类推。现在 1! 为 1，可据此计算 2!，根据 2! 可以计算 3!……根据上述算法，可以通过递归调用求解 n!。

本实例中，先定义一个利用递归调用求阶乘的函数，然后在主函数中定义一个变量保存用户输入的值，调用阶乘函数，计算用户输入数字的阶乘，最后输出结果。代码如下：

#include <iostream>
using namespace std;
long Fac(int n)  //定义 Fac()函数，计算 n 的阶乘
{
    if(n==0)  //如果 n 为 0，返回 1
        return 1;
    else  //如果 n 不为 0
        return n*Fac(n-1);  //返回当前数与前一个数的乘积，此处递归调用了函数自身
}
int main()
{
    int n;
    long f;
    cout << "please input a number" << endl;
    cin >> n;  //输入一个自然数
    f=Fac(n);  //调用 Fac()函数，求输入数的阶乘
    cout << "Result: " << f << endl;
}

程序中通过递归调用 Fac() 函数计算 n 的阶乘。程序运行结果为：

please input a number
4
Result: 24

在上面的递归函数中，如果传递的参数很大，会导致堆栈溢出。因为每调用一次函数，系统都需要为函数参数分配一个堆栈空间。为避免内存溢出，建议用循环乘积的方式求解大数的阶乘 n!。

【实例 2】利用 for 循环求解 n 的阶乘，代码如下：

#include <iostream>
using namespace std;
typedef unsigned int UINT;  // 自定义类型 UINT，用于表示自然数（即无符号整型数）
long Fac(UINT n)  // 定义 Fac()函数，计算 n 的阶乘
{
    long ret = 1;  // 定义 ret，表示阶乘计算结果
    for(int i=1; i<=n; i++)  // for 循环，累计乘积，计算阶乘
    {
        ret *= i;
    }
    return ret;  // 返回结果
}
int main()
{
    int n;
    long f;
    cout << "please input a number" << endl;
    cin >> n;  // 输入一个自然数
    f = Fac(n);  // 调用 Fac()函数，求输入数的阶乘
    cout << "Result: " << f << endl;
}

C++递归函数的用法（附带实例）

相关文章