小白学python第56天之函数递归(难点重点)(1)

编程思想：如何利用数学模型，来解决对应的需求问题；然后利用代码实现对应的数据模

算法：使用代码实现对应的数学模型，从而解决对应的业务问题

递归算法：递推算法是一种简单的算法，即通过已知条件，利用特定条件得出中间推论，直至得到结果的算法。递推又分为顺推和逆推。

顺推：通过最简单的条件，然后逐步推演结果

逆推：通过结果找到规律，然后推导已知条件

1   1    2    3    5    8    13    21   ...

① ② ③  ④  ⑤  ⑥ ...

第1位为1，第2位为1，第3位为2 = 1 + 1，第4位为3 = 2 + 1，依次类推...第n位结果为多少？

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

提出问题：求斐波那契数列第15位的结果？

分析：f(15) = f(14) + f(13)

f(14) = f(13) + f(12)

f(13) = f(12) + f(11)

...

f(4)   =  f(3) + f(2)   = 3  +  1

f(3)   =  f(2) + f(1)   = 2

f(2)  =   1

f(1)   =   1

递推算法：使用while循环或for循环

程序调用自身的编程技巧称为递归（ recursion）。递归做为一种算法在程序设计语言中广泛应用，它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解，递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。

递归有两个非常重要的概念：

① 递归点：找到解决当前问题的等价函数（先解决规模比当前问题小一些的函数，依次类推，最终实现对问题的解决） => 有递有归

② 递归出口：当问题解决的时候，已经到达（必须存在）最优问题，不能再次调用函数了

注：如果一个递归函数没有递归出口就变成了死循环