题目描述：

斐波那契数列是一个经典的数列，数列中的每一项都是前两项的和。数列的定义如下：

你需要编写一个递归函数来计算斐波那契数列的第$n$项。

输入：

输入一个整数 $n$，$0<=n<=30$，表示要求斐波那契数列的第 $n$ 项。

输出：

输出一个整数，表示斐波那契数列的第$n$项的值。

样例输入 1：

5

样例输出 1：

5

样例输入 2：

8

样例输出 2：

21

【递归1】斐波那契数列

前言

递归:

1. 递归

递归是一种函数调用自己的编程技巧。递归的基本思想是将一个复杂的问题分解为更简单的子问题，直到子问题的规模足够小，能够直接解决。递归通常由两个部分组成：

• 终止条件：递归的终止条件，防止无限递归。
• 递归调用：将当前问题转化为更小规模的同类问题，并在其上进行求解。

题解

接下来主要通过这道基本的递归求斐波那契数列的题来讲解递归的用法。

我们先来看一下斐波那契数列的定义:

我们从上述递归的基本构成可知，递归函数是需要有一个终止条件的，如果没有终止条件那么递归就会死循环。斐波那契数列的定义就已经告诉我们该递归函数的终止条件就是:$F(0)=1$和$F(1)=1$,即当递归到$n==0$时函数就要return 0,递归到$1$时就要return 1

如下:

if n == 0:
    return 0  # 斐波那契数列的第0项
if n == 1:
    return 1  # 斐波那契数列的第1项项

然后我们再思考如何实现递归函数，即如何在函数内部，调用函数本身。从斐波那契的公式可得:

那么显然我们要调用的函数自己本身就是$n-1$和$n-2$,即:

return fibonacci(n - 1) + fibonacci(n - 2) // 递归计算F(n)

上图是一个完整的递归过程，绿色箭头表示递归的过程，红色箭头表示回溯的过程，函数不断调用自己，当到达递归边界时便开始回溯，同时返回递归调用的结果，最后再回溯到最开始的函数从而返回答案。

递归的过程对于初学者来说可能比较抽象，建议初学时自己结合代码画图便于理解。

代码

# 递归函数计算斐波那契数列
def fibonacci(n):
    if n == 0:
        return 0  # 斐波那契数列的第0项
    if n == 1:
        return 1  # 斐波那契数列的第1项
    return fibonacci(n - 1) + fibonacci(n - 2)  # 递归计算F(n)

# 主函数
if __name__ == "__main__":
    n = int(input())  # 输入整数n
    print(fibonacci(n))  # 输出斐波那契数列的第n项

例如$fibonacci(5)$的递归过程如下图:

最开始函数调用f(5)然后到左子节点的f(4)然后到左子节点的f(3)，然后到左子节点的f(2),然后回溯，再进入右子节点的f(1)......以此类推