001.【递归算法】

admin

编程语言中，我们习惯将函数（方法）调用自身的过程称为递归，调用自身的函数称为递归函数，用递归方式解决问题的算法称为递归算法。

函数（方法）调用自身的实现方式有 2 种，分别是：
1) 直接调用自身，例如：

[C++] 纯文本查看 复制代码

int funciton(/*...*/) {
    //......
    //调用自身
    function(/*...*/);
    //......
}

2) 间接调用自身，例如：

[C++] 纯文本查看 复制代码

int funciton1(/*...*/) {
    //......
    //调用另一个函数
    function2(/*...*/);
    //......
}
int function2(/*...*/) {
    //......
    //调用function1()函数
    funciton1(/*...*/);
    //......
}

程序中，function1() 函数内部调用了 function2() 函数，而 function2() 函数内部又调用了 function1() 函数。也就是说，function1() 函数间接调用了自身。

设计递归函数时，我们必须为它设置一个结束递归的“出口”，否则函数会一直调用自身（死循环），直至运行崩溃。接下来我们以“用递归方式求 n! ”为例，给大家展示一个正确的递归函数。

n! 指的是求 1*2*3*...*n 的值，如下 C 语言程序中的 factorial() 就是实现求 n! 的递归函数：

[C++] 纯文本查看 复制代码

#include <stdio.h>
int factorial(int n) {
    //递归的出口
    if (n == 1 || n == 0) {
        return 1;
    }
    //函数调用自身
    return n * factorial(n - 1);
}
int main()
{
    int n;
    scanf("%d", &n);
    printf("%d! = %d", n,factorial(n));
    return 0;
}