面试后端开发工程师中有一个很重要的环节，手写代码。一般第一题都比较简单，考察常见的算法和代码规范。递归可以很好的考验求职者计算机基础和算法基本功。
百科定义程序调用自身的编程技巧称为递归。简单的定义: “当函数直接或者间接调用自己时，则发生了递归.” 说起来简单, 但是理解起来复杂, 因为递归并不直观, 也不符合我们的思维习惯,。我以斐波那契数列作为例子说明一下递归。
斐波纳契数列，又称黄金分割数列，指的是这样一个数列：1、1、2、3、5、8、13、21.....
观察分析数列之后，很容易就得出F(n) = F(n-1)+F(n-2) (n>1)规律。从而写出以下函数，解决了问题。
但仅仅就这样吗？有的面试官心情好，提示你，“检查一下，看看代码有优化的空间吗？”。遇到严格一点的面试官，你的这次面试就基本结束了。回头在来看上面的程序，当n很小时候，没问题。但是当n>=100的时候，在跑上面的程序，电脑可能会一段时间没反应，原因是上面程序的函数占用了大量CPU的资源，而且还耗尽了内存。优化方案如下：
在此题中，将递归转换为循环，可以大大提升效率。原因是循环避免了一系列函数调用和返回中所涉及到的参数传递和返回值的额外开销。这才是面试官想要的答案之一。
从上面的例子分析，递归的优点很明显，简洁，代码量少。但是要确定好边界，否则很容易失误。在树的前序，中序，后序遍历算法中，递归的实现明显要比循环简单得多。
递归的缺点，函数自身多次重复调用，产生了很多的额外开销。若控制不好边界，会产生导致计算机内存不足，大大降低效率。
这是一个经典题目，考察了内存，递归，循环编程基础。不会的同学请认真掌握，争取面试必胜，早日拿到心仪offer~
联系客服
