【Day 18】递回 Recursion(续) 费氏数列与递回的限制

前言

昨天跟大家介绍了递回的概念，以及在阶乘的实际应用，今天要来接着继续介绍，如果还不太熟悉的可以看一下前一天的文章喔！

费氏数列 Fibonacci sequence

在数学上，费波那契数是以递回的方法来定义：

f(0) = 0
f(1) = 1
f(n) = f(n-1) + f(n+1)

每一项都是前两项的和，0 为第 0 项，不是第 1 项！
底下为前几项费氏数列的值

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377 ,610, 987……

def Fibonacci(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        return Fibonacci(n - 2) + Fibonacci(n - 1)
for i in range(10):
    print(Fibonacci(i), end = ' ')

在上面的程序中，一个函式就呼叫自己两次，然後每次呼叫都会占用到记忆体的空间，只做小数字的话还好，但是如果运算到数字非常大的时候，每个函式会再呼叫两个函式，这样叠加下来就会耗费非常多的时间。

计算 f(n) 会用到 f(n-1) 和 f(n-2)，然後 f(n-1) 会再用到 f(n-2) 和 f(n-3)，所以 f(n-2) 就会被呼叫两次，最後的 f(1) 和 f(0) 会被疯狂呼叫，狂占记忆体，浪费时间也浪费空间。

Recursion 的限制

如果程序设计不佳，导致无穷回圈或是跑的次数太多，电脑的记忆体就会被塞满，所以为了防止这件事情，Python 对於递回有次数限制，预设的次数可以透过 sys 这个 module 的函式来查看，预设为 3000，若超过这个次数会出现 RecursionError: maximum recursion depth exceeded 的 error

import sys
sys.getrecursionlimit()

待续...