0%

算法之递归

递归是一种应用非常广泛的算法,在很多的数据结构和算法的编码中都会用到,理解递归是非常重要的。

递归在平时的生活中也是非常常用的,当你排队的时候需要知道自己排在第几个位置,而前面的人又比较多,你不能自己数出来,就可以询问你前一个人他的位置,在他的位置基础上加一便是你的位置,那如果他也不知道他的位置呢,就可以用同样的方法,继续向前询问,直到第一个人,第一个人就不用往前问了,他直到自己是第一个,这个过程就是一个递归的过程。

去问的时候叫做“递”,返回来的时候叫做“归”,假设自己是第n排,求自己位置的函数为f(n),f(n-1)就是前一个人的位置,我们的位置就是f(n-1)+1,同样前一个人的位置也可以用这个公式来计算, 直到第一个人f(1)=1,这一整套流程便是递归的实际利用,编写成代码如下

在编写递归代码的时候,有两点必要的条件:

  • 一个问题可以分解为多个结构相同,规模不同的子问题。
  • 存在终止条件。

如果结构不同,那就不能构造递归了;如果不存在终止条件的话,将会无限循环,看上面的那个例子,它的终止条件就是执行到第一个人的时候,开始往后返回。


递归就这样完成了,上面这个例子是只有一个递归调用的分支,还是比较好理解的,如果有多个递归分支的话,单纯靠人脑是很难理解清楚的,计算机比较适合做重复的工作,我们如果一环一环往递归里走的话,很快就迷糊了,唯一的方法就是自己屏蔽掉其中细节,只把握好第一个递归公式的构造和终止条件的判断,就能更好的理解清楚递归了。

假如有n阶台阶,可以每次走一个台阶或两个台阶,请问走完n阶楼梯有多少种走法?

  • 如果有一层台阶,(1),有一种.
  • 如果有两层台阶,(1,1)、(2),有两种
  • 如果有三层台阶,(1,1,1)、(1,2)、(2,1),有三种
  • 如果有四层台阶 ,(1,1,1,1)、(1,1,2)、(1,2,1)、(2,1,1)、(2,2),有五种
  • 如果有五层台阶 ,(1,1,1,1,1)、(1,1,1,2)、(1,1,2,1)、(1,2,1,1)、(2,1,1,1)、(1,2,2)、(2,1,2)、(2,2,1),有八种
  • 以此类推

举几个例子,就可以很明显的发现,从第三层开始,每一层都是前两层的次数相加,所以我们就可以得到公式f(n) = f(n-1)+f(n-2) ,通过举例子是最容易理解的一个方式,实际上去理解的方法有很多种,可以自己去尝试,你可以用递归的想法去一层层跑一下,就会发现整体的困难程度是非常大的。

所以将其转换为代码就如下图所示


在写递归代码的时候,还需要注意两个问题:

  • 警惕堆栈溢出
  • 警惕重复计算

先说堆栈溢出,在函数调用时,会使用栈来保存临时变量,每进行一次函数调用,就会将临时变量封装后压入内存栈,这个栈的大小是由系统来决定的,如果递归太深,压入栈中的数据是非常多的,就会有堆栈溢出的风险;解决办法就是在递归函数中加入一个判断条件,来判断递归的深度,如果达到了某一个值,就直接返回报错。

另一个就是重复计算,当我们在计算f(5)的时候会计算f(4)和f(3),在计算f(4)的时候还需要计算f(3),f(3)就被重复计算了,为了避免重复计算,可以通过数据结构来记录已经计算过的值,在计算前先进行判断,如果计算过就直接将值返回。

为了避免这些情况,也可以将递归代码改为迭代循环的非递归方式,就是使用循环的方式来进行处理。


参考文档

极客时间-数据结构与算法之美