递归算法的基本思想：就是程序中不断反复的调用自身来解决问题的方法。这里强调的重点是调用自身，就是要求解的问题能够被分解成多个相同的小问题这样通过多次递归调用，便可以完成求解。

递归：函数（方法）调用其自身的过程。

递归函数：调用自身的函数。

递归算法：用递归的方式解决问题的算法。

函数（方法）调用自身的实现方式有2种，分别是：

直接调用自身

1
2
3
4
5
6
7
static int function(/*...*/)
{
    // ......
    // 调用自身
    function(/*...*/);
    // ......
}

间接调用自身

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
static int function1(/*...*/)
{
    // ......
    // 调用另一个函数
    function2(/*...*/);
    // ......
}

static int function2(/*...*/)
{
    // ......
    // 调用 function1() 函数
    function1(/*...*/);
    // ......
}

设计递归函数的时候，我们必须为它设置一个结束递归的“出口”，否则函数会一直调用自身，造成死循环，直到系统崩溃。以下为一个使用递归算法求解 n！的例子。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
internal class Program
{
    private static void Main(string[] args)
    {
        string input = Console.ReadLine();
        int n = int.Parse(input);
        Console.WriteLine($"{n}的阶乘是：{Factorial(n)}");
    }
    
    public static int Factorial(int n)
    {
        // 递归结束的出口
        if(n == 1 || n == 0)
        {
            return 1;
        }
        // 调用自身
        return n * Factorial(n - 1);
    }
}

输入：3

输出结果为：

3的阶乘是：6

递归算法的底层机制

递归算法的底层机制实现其实就是通过数据结构中栈实现的，使用栈结构保存调用者的状态信息，包括暂停时局部变量的值、寄存器中保存的数据等等。如下图所示：

递归算法的栈

递归算法的经典应用

斐波那契数列

前两个数的值分别为 0 、1 或者 1、1；

从第 3 个数字开始，它的值是前两个数字的和；

如：1 1 2 3 5 8 13 21 34…

斐波那契数列

递归算法实现斐波那契数列
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
internal class Program
{
    private static void Main(string[] args)
    {
        string input = Console.ReadLine();
        int n = int.Parse(input);
        Console.WriteLine($"{n}个数的斐波那契数列为：");
        for (int i = 1; i <= n; i++)
        {
            Console.Write("{0} ", Fibonacci(i));
        }
    }
    
    private static int Fibonacci(int n) // index 索引第几个数
    {
        if (n == 1 || n == 2) // 如果是第1个和第2个数则都返回1
        {
            return 1;
        }
        // 返回前两数之和
        return Fibonacci(n - 1) + Fibonacci(n - 2);
    }
}

输入：10

输出结果为：

10个数的斐波那契数列为：
1 1 2 3 5 8 13 21 34 55