【Day 17】递回 Recursion

前言

在解题时可能会遇到一些问题不是正常的回圈就可以解决的，可能需要用到前面的答案来运算，像是计算阶乘、费氏数列等等，就会使用到递回了！

递回 Recursion

把一件复杂的工作拆分成很多简单的小工作来处理，这个方法称为 Divide and Conquer approach 分治法。

递回就是根据这个概念形成的，把一个大问题拆成很多个中问题，再把这些中问题拆分为许多早小问题，这些小问题都用同样的 function 来解，用这个方式来解决大问题就称作递回 Recursion。

这种呼叫自己的动作，就被认为具有递回的性质，为了避免函式无止尽的呼叫自己，形成无穷回圈，所以需要有终止条件，来明确定义什麽时候该结束。

阶乘 Factorial

数学中的阶乘符号用 ! 来代表，n! = 1 * 2 * ... * n

以数学方式表示 n 阶层的话如下图

可以看出 n! = n * (n - 1)!，我们就可以用这个概念来写出递回的程序。

0! = 1
1! = 1
n! = n * (n - 1)!, n >= 1 

def factorial(n):
    if n == 0 or n == 1:
        return 1
    else:
        return n * factorial(n - 1)

print(factorial(5))

呼叫的为 5! 所以可以拆分为 5 * 4! 再把 4! 拆分为 3!...依此列推，就可以运算出阶乘了

今天先介绍到阶乘，明天继续来介绍同样很有名的费氏数列，还有递回的一些限制，明天见

待续...