递归算法（上）

什么是递归

在函数内部，是可以调用其他函数的。如果一个函数在内部调用自身，就称这个函数就是递归函数。

举个例子：

实现一个可以自定义重复打印你好的函数。

要实现重复打印，可能我们立马就会想到使用循环。

如果要求不能使用循环呢，那我们就可以通过下面的方法来实现。

原理很好理解，就是不断的调用自身，如果前面不加上if条件判断，理论上是会陷入死循环的，但是实际上递归到一定次数（最大递归次数）就会报错停止。

递归有什么用

知道递归是怎么回事，那么递归有什么实际用处嘛，或者说有什么独特之处。比如上面的例子用循环就很方便，我为什么还要学习递归这种方法呢？

递归实际上是一种解决问题的方法，将问题分解为更小的子问题，直到得到一个足够小的问题可以被很简单的解决。对于非常简单的问题，可能我们使用循环就非常方便，比如前面的那个案例，但是有些问题如果使用循环，可能就会非常麻烦，或者解决方案很难让人理解清楚里面的逻辑。

因为递归函数是找到最小问题的解决方法，然后只要不断使用这个方法就可以解决了，所以递归函数的优点是定义简单，逻辑清晰。理论上，所有的递归函数都可以写成循环的方式，但循环的逻辑不如递归清晰。

下面就通过一些案例来实际感受一下。

递归的应用

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)用递归的方式写出来就是：

在计算机中，函数调用是通过栈（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)

模仿Fib函数当i = 5的执行过程。

（图片来源于大话数据结构）

函数如果调用自己比较难理解，可以看作调用其它函数，只不过和自己长的相同而已相同而已。

3.螺旋线

每一次都是前进length长度，然后右转，长度需要不断的减小，直到小于5停止。

(全文完)