常见算法介绍 ---- 递归算法介绍（C++描述）

【必要的基础知识】

        分治法（Divide and Conquer）常用来逐一拆解复杂的问题，核心思想就是将一个难以直接解决的大问题依照相同的概念分割成两个或更多的子问题，以便各个击破。

【递归简介】

        通过重复将问题分解为同类的子问题而解决问题的方法，具体指的是函数自己调用自己，从而使求解范围逐步缩小。

【递归条件】
        1、 可以反复执行的递归过程
        2、跳出执行过程的出口

【示例代码·壹】

        使用递归算法计算10的阶乘。

#include <iostream>
using namespace std;
int factorial(int);
int main()
{
    //求10的阶乘 10!
    cout << "10! = " << factorial(10) << endl;
    return 0;
}
 
int factorial(int i)
{
    static int result = 0;
    if (i == 0)
    {
        return 1;
    }
    result = i * factorial(i - 1); // n!=nx(n-1)x(n-2)x...x1
    return result;
}

【示例输出·壹】

10! = 3628800

【示例代码·贰】 

利用递归算法求斐波那契数列的第n项值。

【附】斐波那契数列的数学性质如下：

        

//斐波那契数列（Fibonacci Polynomial）
#include <iostream>
using namespace std;
int Fib(int);
int main()
{
    //求斐波那契（Fibonacci）数列的第n项
    cout << "Fib(10) = " << Fib(10) << endl;
    return 0;
}
 
int Fib(int i)
{
    static int result = 0;
    if (i == 0)
    {
        return 0;
    }
    else if (i == 1)
    {
        return 1;
    }
    result = Fib(i - 1) + Fib(i - 2); // F(n)=F(n-1) + F(n-2)
    return result;
}

【示例输出·贰】

Fib(10) = 55