C++函数递归

C++函数递归教程

函数递归就是一个函数在函数体内又调用了自身，我们称为函数的递归调用。

C++函数递归条件

执行一个函数时，就创建一个新的受保护的独立空间(新函数栈)。
函数的局部变量是独立的，不会相互影响。
递归必须向退出递归的条件逼近，否则就是无限递归了。
当一个函数执行完毕，或者遇到 return，就会返回，遵守谁调用，就将结果返回给谁，同时当函数执行完毕或者返回时，该函数本身也会被系统销毁。

C++函数递归详解

语法

type funcName(param)
{
    if (param == cond)
    {
        return;
    }
    funcName(param2);
}

说明

我们定义了一个函数 funcName，该函数传递一个参数，接着，在函数体里面我们使用 if 判断 当参数满足一定的条件，就直接 return，否则则继续调用函数自己。

这里的 if 条件就是函数递归的出口，这个非常重要，如果没有这个递归的出口，那么这个递归就会一直执行下去。

案例

C++函数递归

C++ 函数递归结束条件

#include <iostream>
using namespace std;
void printNum(int num)
{
	if (num > 2)
	{
        num--;
        printNum(num);
    }
	cout << "Num = " << num << endl;
} 
int main()
{
	cout << "嗨客网(www.haicoder.net)\n" << endl;
	printNum(4);
	return 0;
}

程序运行后，控制台输出如下：

10_c语言访问数组元素.png

我们定义了一个 printNum 函数，该函数的参数是 int 类型 的数字，在函数体里面我们使用 if 判断，如果当前参数的值大于 2 的话，我们就首先将当前参数的值减一，然后再次调用自己。

如果当前参数的值不大于 2 的话，那么就打印当前参数的值。这里的 if 条件里面的逻辑就是函数 printNum 自己调用自己，这就构成了递归调用。同时不满足 if 条件的情况，就是递归调用的出口。

C++函数递归

C++ 函数递归，实现求阶乘

#include <iostream>
using namespace std;
int factorial(int num)
{
	int result = 0;
    if (num > 0)
	{
        result = num * factorial(num-1);
        return result;
    }
    return 1;
}
int main()
{
	cout << "嗨客网(www.haicoder.net)\n" << endl;
	int factorialResult = factorial(5);
	cout << "factorialResult = " << factorialResult << endl;
	return 0;
}

程序运行后，控制台输出如下：

11_C函数递归.png

我们定义了一个 factorial 函数，该函数的参数是一个数字，在函数体里面我们使用 if 判断，如果当前参数的值大于 0 的话，我们就再次调用自己，并且参数的值是当前值减一，最后返回计算的结果。

如果当前参数的值不大于 0 的话，那么就直接返回 1。这里的 if 条件里面的逻辑就是函数 factorial 自己调用自己，这就构成了递归调用。同时不满足 if 条件的情况，就是递归调用的出口。

C++函数递归

C++ 函数递归，实现斐波那契数列

#include <iostream>
using namespace std;
int fibonacci(int num)
{
	int result = 0;
    if (num <= 1)
	{
        result = 1;
    }
	else
	{
        result = fibonacci(num-1) + fibonacci(num-2);
    }
    return result;
}
int main()
{
	cout << "嗨客网(www.haicoder.net)\n" << endl;
	int fibonacciResult = fibonacci(5);
	cout << "fibonacciResult = " << fibonacciResult << endl;
	return 0;
}

程序运行后，控制台输出如下：

12_C函数递归.png

我们定义了一个 fibonacci 函数，该函数的参数是 int，返回值 也是 int，在函数体里面我们使用 if 判断，如果当前参数的值小于等于 1 的话，那么我们就将结果赋值为 1，否则我们就再次调用自己。

C++函数递归总结

函数递归就是一个函数在函数体内又调用了自身，我 10_C函数递归.png 们称为函数的递归调用。函数递归最重要的就是一定要找到递归调用的出口。