问题:

在数学与计算机科学中，函数的定义中使用函数自身的方法叫做递归。

举个实际的例子，我们来计算阶乘 n! = 1 x 2 x 3 x ... x (n-1) x n，那么 n! 就等于 n x (n-1)!，(n-1)! 等于 (n-1) x (n-2)!，以此类推最后算到 1。

所以我们可以像下面这样计算阶乘：

def fact(n):
  if n == 1:
    return 1
  return n * fact(n - 1)

阶乘函数 fact() 里只要处理 n 为 1 的情况，其它情况下只要计算 n * fact(n-1)，fact(n-1) 又会计算 (n-1) * fact(n-2)，直到 n 为 1 时结束并得到结果。

是不是有点晕了呢？没关系，我们以 fact(3) 为例看一下执行过程：fact(3) 的值为 3 * fact(2)，这时会去计算 fact(2)。fact(2) 的值为 2 * fact(1)，然后再去计算 fact(1)。而 fact(1) 的值为 1，因此，fact(2) 的值为 2，最后便能得到 fact(3) 的值为 6。

可以看到，递归的结果依赖下一层的计算结果，一层层嵌套的下去。所以递归必须有结束条件，否则将无限调用自身导致栈溢出报错。当然，嵌套层数过多也会导致栈溢出报错，比如上面的 fact(2000) 也会导致栈溢出报错，这也是递归的缺陷。

好了，科普结束。接下来请你用递归计算斐波拉契数列。

在数学上，斐波那契数列是以递归的方法来定义的：

用文字来说，就是斐波那契数列由 0 和 1 开始，之后的斐波那契数就是由之前的两数相加而得出。前几个斐波那契数是：

0 1 1 2 3 5 8 13 21 34 55 89 144 233 ......

答案:

def fibo(n):

if n<=1:

return n

else:

return fibo(n-1) + fibo(n-2)

print(fibo(4))

print(fibo(23))