image
什么是递归
在函数内部，是可以调用其他函数的。如果一个函数在内部调用自身，就称这个函数就是递归函数。
举个例子：
实现一个可以自定义重复打印你好的函数。
要实现重复打印，可能我们立马就会想到使用循环。
image
如果要求不能使用循环呢，那我们就可以通过下面的方法来实现。
image
原理很好理解，就是不断的调用自身，如果前面不加上if条件判断，理论上是会陷入死循环的，但是实际上递归到一定次数（最大递归次数）就会报错停止。
image
递归有什么用
知道递归是怎么回事，那么递归有什么实际用处嘛，或者说有什么独特之处。比如上面的例子用循环就很方便，我为什么还要学习递归这种方法呢？
递归实际上是一种解决问题的方法，将问题分解为更小的子问题，直到得到一个足够小的问题可以被很简单的解决。对于非常简单的问题，可能我们使用循环就非常方便，比如前面的那个案例，但是有些问题如果使用循环，可能就会非常麻烦，或者解决方案很难让人理解清楚里面的逻辑。
因为递归函数是找到最小问题的解决方法，然后只要不断使用这个方法就可以解决了，所以递归函数的优点是定义简单，逻辑清晰。理论上，所有的递归函数都可以写成循环的方式，但循环的逻辑不如递归清晰。
下面就通过一些案例来实际感受一下。
递归的应用
1.计算阶乘n! = 1 x 2 x 3 x ... x n
本案例来源于廖雪峰的网站
factorial(n) = n! = 1 x 2 x 3 x ... x (n-1) x n = (n-1)! x n = factorial(n-1) x n
所以，factorial(n)可以表示为n x factorial(n-1)，只有n=1时需要特殊处理。
于是，factorial(n)用递归的方式写出来就是：
image
在计算机中，函数调用是通过栈（stack）这种数据结构实现的，每当进入一个函数调用，栈就会加一层栈帧，每当函数返回，栈就会减一层栈帧。
===> factorial(5)
===> 5 * factorial(4)
===> 5 * (4 * factorial(3))
===> 5 * (4 * (3 * factorial(2)))
===> 5 * (4 * (3 * (2 * factorial(1))))
===> 5 * (4 * (3 * (2 * 1)))
===> 5 * (4 * (3 * 2))
===> 5 * (4 * 6)
===> 5 * 24
===> 120
2.斐波那契数列
列举可以得出0，1，1，2，3，5，Fib(n-2)，Fib(n-1)，Fib(n);除了第一项和第二项都为1外（0忽略）,需要单独拿出来，其它项都满足Fib(n)=Fib(n-2)+Fib(n-1)
image
模仿Fib函数当i = 5的执行过程。
image
（图片来源于大话数据结构）
函数如果调用自己比较难理解，可以看作调用其它函数，只不过和自己长的相同而已相同而已。
3.螺旋线
每一次都是前进length长度，然后右转，长度需要不断的减小，直到小于5停止。
(全文完)
长按二维码，加关注！叶子陪你玩
欢迎转载，转载请注明出处！
欢迎关注公众微信号：叶子陪你玩编程
分享自己的python学习之路
网友评论