第五章：PHP编程思想提升篇——递归思想
更新于：2017-04-19 21:57:36
递归是一种不太好理解的编程思想，很重要，有些问题离开了递归，还真就解决不了。
递归思想的一个基本形式是：在一个函数中，有至少一条语句，又会去调用该函数自身。
但是，从代码角度来说，如果单纯是函数内部调用函数本，则会出现“出不来”的现象。
则我们就必须再来解决下一个问题：怎么终止（停止）这种调用——找到递归函数的出口。
做一个简单的代码演示：
看结果：
从代码第9、10行可看到，满足了if条件，函数又调用了自己。所以，递归的核心思想就是“自己调用自己……自己调用自己”，就像一个大循环。
有朋友可能会想，递归其实就是在不停地循环，那我用for循环、while循环也可以实现上面的功能，所以递归看起来也没啥稀奇的。
其实不是，有些功能，for循环就实现不了，必须依靠递归。比如遍历一个数组，这个数组可以像这样的：
没有任何规律，都不清楚它是几维数组，用for循环根本实现不了。假如说$arr是个100维的数组，程序中for循环需要嵌套100次，这样的代码就算写出来也是不能要的。
递归就很轻松地能实现，看代码：
上面的例子也不太难理解吧。
for循环和递归还有一大不同之处：
for循环循环三次，流程是这样的1->2->3，跳出循环
递归三层深度，流程是这样的1->2->3->2->1，函数结束，递归它有往回返的过程。
再举一例子帮助理解：
写一个递归函数，该函数可以计算一个正整数的阶乘：
数学基础：
A： 1的阶乘是1
B： 大于1的数的阶乘，是这个数减1的数的阶乘，乘以该数的结果。
比如：要求6的阶乘：
则定义一个函数jiecheng(){.....};该函数可以计算n的阶乘
递归思想的总结：
为了解决一个“大”问题，根据现实逻辑，该问题可以通过比它小一级的同类问题的答案而“轻松得到”。小一级的问题又可以通过更小一级的问题而轻松得到，依次类推——直到“最小问题”，通常就是一个已知数（答案）。
递归思想的图示
补充：
如果能用其他方式实现的功能，就不要轻易用递归。递归是很耗费资源的，分析下：
正常情况下，程序调用完一个函数获得值再去调用另一函数。假如调用完a函数，再去调用b函数，调用b函数前，a函数占用的内存已释放。
而递归呢，函数调用函数自己，开辟新内存空间，可上一层的函数没有结束，它还在等返回值，没有内存空间被释放。调用一次，就会在内存中多占用空间，调用深度越深内存占用得越多，有可能造成内存溢出。
好比我们用浏览器访问网页，看完一个网页关闭了接着看下一个，就算看一天浏览器都没有问题，不会卡的。可如果看完一个网页也不关闭就去看下一个，慢慢得浏览器就会卡死的。递归的道理和这是一样的。
阶乘那个例子用递推的方式也能实现，或者用“尾递归”也可以实现。关于“尾递归”，楠神不讲解了，真的不好理解。递归本身在实际开发中用的也不是太广泛，但挺重要，把基础的递归知识学会就OK，前期学习不宜把过多的时间用于研究难懂的东西。
可变函数在递归函数里的应用：
一个递归函数如果要改名字的话，不仅要改函数体外的名字（function name(){}），是不是还得去它的函数体里找下调用自己的地方把名字改掉，不然就会出问题的。其实定义一个递归函数，可以这样写：
看第10、11行。
必须要把魔术常量先赋值给一个变量，第11行才能实现可变函数。
做一些递归的练习题：
1、数列如下：【1】，【2】，3，6，9，18，27… ，用递归求第20项的值是多少？（注意，规律就是第n个数是第n-2个数的3倍，已知第一个是1，第二个是2）。
2、猴子吃桃问题：
有一堆桃子，猴子第一天吃了其中的一半，并再多吃了一个！
以后每天猴子都吃其中的一半，然后再多吃一个。
当到第十天时，想再吃时（即还没吃），发现只有1个桃子了。
问题：最初共多少个桃子？
分析：
天 数量
10 1
9 (1+1)*2=4
8 (4+1)*2=10
7 (10+1)*2=22
。。。。。。
第n天 （第n+1天的个数+1）*2
提示：用递归或递推解决问题。