前两节我们讲解了函数的使用以及函数的重要特性:静态变量。那么对于函数而言还有没有什么必须要讲的呢?
你可能已经猜到了,就是 函数调用 自身,是的,调用自身这一特性实在是令人匪夷所思,这是一个鸡生蛋,蛋生鸡的问题。
在程序中,函数调用自身的时候就出现了另外一个名词:递归!这个词用的很普遍,你应该也有所耳闻,百度百科中这样解释递归:
是的,调用自己这样的编程技巧,称为递归,请注意,这里是一种编程技巧,同时他也是一种算法被广泛使用。那么它的使用环境和条件又是什么呢?当一个大的复杂的问题不好解决,但是层层细分为小问题就方便解决的时候,寻找规律,发现临界点,就是递归的使用条件和技巧。
比如说,我们举个简单的例子,计算裴波那切数中第n个数。
我们知道,裴波那切数是有规律的,其遵循本位数值等于前两位数值之和,那么我们假定第一个数是1则第二个也是1,第三个就是1+1=2,第四个就是1+2=3,第五个就是2+3=5 即
1 1 2 3 5 8 13 21 34 55……
我们发现猛然的让我们计算第n个数是多少,我们并不能立刻得出结论,因为这和前两个数有关,那我们需要先计算第n-1个数和第n-2个数,可想而知,这样一来,就把问题往前推进了一步,当然无限前推也得有个尽头啊,什么时候是临界点呢?就是当n<=2的时候这个值是1,看来我们明白了,只要总结出有个公式即可。
f(n)=f(n-1)+f(n-2);(若n<=2,f(n)=1)
既然有了这个公式,编程代码就自然而然出来了
好,这是我们初试牛刀的尝试,如果说难度升级一点,是不是又能够理解呢?
接下来我们将举个更加复杂的例子,查询无限极分类的所有子节点。
比如这个 树形结构
用数组表示节点与父节点的关系如下:
然后我们要书写一个函数能从该对照关系中获取某个节点的所有子孙节点,那么又该如何处理呢?
这里我们要学会分析节点,某个节点可能有多个子节点,子节点又可能有子节点,那么这样的情况下就需要做全部的节点遍历了,从最左边开始找到最右边,我们看代码
这里利用了递归和静态变量合作,完成了这个效果,比如
我们可以看到正是这样从最左到最右的顺序完成的遍历。
那么这段程序的核心是什么呢?
就是遍历数组,在数组中查询子孙节点的子孙节点,当找到以后,重新赋值当前要查询的节点,采用递归方式走下去,这样就能走进深度的遍历。
这段代码有个地方可以完善一下,修改如下:
可以修改为
这样一步操作,虽然很简单,但是在大数据的循环时,能迅速的帮助结构体降低循环次数,因为筛选的原数组,每少一个,下次循环就会少一次,能够大大的降低循环次数,减少之前找到了也要循环的无效循环,提高函数效率!
关于递归,我想这个例子需要好好的思考,吃透,那么递归方面的问题基本上就不大了,树形结构用在了很多业务模型上,比如无限极分类,无限极回复,无限极分佣等等(当然现在国家要求只能做三级分佣)等等。
掌握递归的精髓就在于掌握递归(这句话本身就是递归)!