由斐波那契数列引发的思考

周末时间,还是不能放松学习~

人一吃饱饭没事干就爱瞎想,你看古今中外的哲学家们,整天思考宇宙人生,从哪来到哪去的问题,要是肚子都没吃饱哪有那闲情去扯这些呢?马斯洛需求层次理论可以了解一下.

等等,好像跑题了,言归正传.话说下午闲来无事,就在某论坛瞎逛,无意之中瞥到了斐波那契数列,于是乎,想起了有一回面试被要求用递归的方式手写求斐波那契数列第n个数......我想了大概15分钟,因为一开始脑子想的都是数组和加for循环的求解思路,突然灵感一现,峰回路转,最终只用3行代码搞定了!写出来的程序是这样的:

private static int fibonacci(int n) {
 if (n <= 2) {
 return 1;
 }
 return fibonacci(n - 1) + fibonacci(n - 2);
 }

突然,我又脑洞大开,何不试试用递归的方式实现在控制台打印九九乘法表咧~

实现在控制台打印输出九九乘法表相信大部分coder刚入门的时候都写过,甚至有些面试场合也会要求手写代码或排序等算法.

面对这个需求,我的第一反应就是用嵌套for循环来解决,写出来的代码是这样的:

 private static void multipTable() {
 for (int i = 1; i < 10; i++) {
 for (int j = 1; j < 10; j++) {
 System.out.print(j + "x" + i + "=" + i * j + " ");
 if (i == j) {
 //换行并跳出当前循环
 System.out.println();
 break;
 }
 }
 }
 }

时间复杂度是O(n^2),代码看似很简洁也实现功能了,但问题就是:逼格不够高!那咋办咧,得想个逼格更高的实现方式,递归,说的就是你!思忖一番,写出的代码长这个样子:

private static void multipTable(int n) {
 if (n == 1) {
 System.out.println("1x1=1");
 } else {
 multipTable(n - 1);
 for (int i = 1; i <= n; i++) {
 System.out.print(i + "x" + n + "=" + i * n + " ");
 }
 System.out.println();
 }
 }

调用的时候传值n=9,嗯,不错,是有递归思想,可还有for循环呀,这么写逼格是提高了一丢丢,然鹅代码不够优雅.咳咳,没办法,平日受够产品经理折磨的我,闲下来还要折磨自己,我已经被生活摧残成这个样子了吗?

仔细捋捋思路,本问的关键是要解决列值和行值能找到一种关系,上一种解决方式找到了关系,就是列值的最大值小于行值,但是是通过for循环来体现的.这次我找到了一种新的关系,9x9,8x8,7x7...1x1,意思是假如现在是最后一行,我计算完后,压进栈中,这时要计算第八行,那怎么进入第八行呢,第九行减一行作为行数,列数等于行数,不就递归调用了吗?

好,行数的问题解决了,那列数呢,从每一行的最后一列计算到第一列怎么搞?你看,列数不是等于行数了嘛,那这个时候在第八行最后一列,是8x8,我让行数不变,列数减一递归调用就能实现了,出口就是列数要d等1,等于1说明已经计算到第一列,要往上一行递归了!

所以,综上所述,行递归函数的出口是row=1,列递归函数的出口是col=1;

row == 1 && col == 1,则是整个递归函数的出口;

最终没有for循环的纯递归版本是这样的:

private static void multipTable(int row, int col) {
 //递归函数的出口
 if (row == 1 && col == 1) {
 System.out.println("1x1=1");
 }
 if (row > 1) {
 if (col > 1) {
 //列递归函数
 multipTable(row, col - 1);
 } else {
 //行递归函数
 multipTable(row - 1, row - 1);
 }
 System.out.print(col + "x" + row + "=" + row * col + " ");
 if (row == col) {
 System.out.println();
 }
 }
 }

总算是搞定了,激动之余,回顾一下写的这些代码,发现了一个问题,也不是所有的算法递归写的代码都更简洁的咯,而且在代码易读性上,for循环更清晰易懂(这个因人而异).除了这些,递归还有什么劣势吗?总结了一下递归的优缺点:

优点：代码普遍更简洁,尤其是在树的遍历算法中.

缺点：

1.递归由于是函数调用自身，而函数调用是有时间和空间的消耗的：每一次函数调用，都需要在内存栈中分配空间以保存参数、返回地址以及临时变量，而往栈中压入数据和弹出数据都需要时间。

2.递归中很多计算都是重复的，由于其本质是把一个问题分解成两个或者多个小问题，多个小问题存在相互重叠的部分，则存在重复计算，如斐波那契数列的递归实现,可以自己用笔在纸上画一下属性图.

3.可能会发生栈溢出，其实每一次函数调用会在内存栈中分配空间，而每个进程的栈的容量是有限的，当调用的层次太多时，就会超出栈的容量，从而导致栈溢出。