浅显的理解

递归是一个在数据结构中非常基本的思想,也是一个非常重要的编程技巧。很多复杂的数据结构的操作其核心思想都是递归。递归的特点之一就是简洁,看起来非常的清晰。另外一个特点就是「绕」,因为它在一直的进行「嵌套」。

递归与递推

和递归思想相对应的就是递推。这么对比着来思考这两个东西是非常有趣的。递归贯彻的是一种「先切割,后合并」的思想,而递推更强调「积少成多」。两种思想是截然相反的,它们是彼此的「逆过程」。所以,很多时候,递归和递归的代码是可以相互转化的。

递归的特点

通过上面和递推的思想进行对比,我们可以知道,递归有两个要素:

  1. 待求解的问题可以被分割为多个小问题
  2. 多个小问题的结果经过合并就是带求解问题的结果

在了解了上述两个要素之外,这里还有一个隐含的因素:待求解问题必须是可分割的,而且是有边界的,不能一直分割下去。所以,递归的三个特点也就呼之欲出了:

  1. 待求解问题可分为个数量有限的子问题
  2. 多个子问题的求解思路一致,可重复
  3. 递归过程一定要有一个终止条件,即最小子问题

如何编写递归代码

无论是递归,还是动态规划,都隐含了「由小见大」的思想。所以,对这类问题,重中之重就是推导出求解公式。除此之外,就是写出一个可靠的边界条件,以便在有限的步骤内求出问题的解。最后才是代码上面的实现。

以斐波那契数列为例:

公式

Fn=Fn-1+Fn-2(n>=2,n∈N*)

边界条件

F0=0,F1=1

代码

1
2
3
4
5
6
func Fibonacci(n int) int {
  if ( n == 1 ) return 1
  if ( n == 0 ) return 0
  
  return f(n-1) + f(n-2)
}

递归的风险

虽然我们可以通过「认真」来规避递归由于代码编写上带来的问题。但是,有些问题,可能是递归与生俱来的。

爆栈

在使用递归的时候,一般都是通过函数嵌套调用的形式。函数的嵌套调用,根据之前我们对堆栈的了解,每一次调用都会分配一定空间的函数栈,以便能够存储一些临时变量。如果此时嵌套层数过多,那么就可能会引起堆栈溢出的情况。

重复计算

编写递归逻辑非常容易出错,甚至有的时候效率会出奇的低。因为在递归计算的过程中,我们的计算步骤有的时候可能会重合。以上面说到的斐波那契数列为例:假设现在 n = 4。

  1. F(4)= F(3) + F(2)
  2. F(3) = F(2) + F(1)

我们发现F(2)其实是被重复计算了,这其实是没必要的。但是如果你将整个递归过程写完,就可以发现 F(1) F(0) 虽然也被重复用到,但是他们仅仅只是一个赋值操作,不会有额外的消耗。借鉴这种思想,我们应该将已经计算出来的结构保存起来,如果之前计算过,那么就用之前的结果。我习惯把这种技巧叫做「记忆化搜索」

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
memory := make(map[int]int)
func Fibonacci(n int) int {
  if ( n == 1 ) return 1
  if ( n == 0 ) return 0
  
  oldValue, ok := memory[n]
  if ok {
	return oldValue
  }
  
  newValue := Fibonacci(n-1) + Fibonacci(n-2)
  memory[n] = newValue
  return newValue
}

由递归至递推

上面已经说到了递归和递推的区别,并且已经知道它们的逻辑可以相互转换。还是以斐波那契数列为例:

1
2
3
4
5
6
7
8
9
func Fibonacci(n int) int {
   prepre, pre := 0, 1
   var result int
   for i := 2; i <= n; i++ {
       result = pre + prepre
       prepre = pre
       pre = result    
   }
}

对边上面递归的过程就可以知道,递归是「由大到小」,递推是「由小到大」

重中之重—递归的思想

其实,在之前学习递归的过程中,我很喜欢手推递归的过程,尤其是那种很冗长的,比如汉诺塔。因为我觉得只有我了解了它每一个步骤,我才真正理解了递归的过程。但其实,这是一个非常大的思维误区。打个比方吧:乔布斯好不容易把IPhone 做的那么轻薄,你偏要给它带个厚重的手机壳。递归之所以看起来简洁,执行起来复杂,是因为人的大脑是不适合一直重复的做一个动作的,如果硬是要这样,几次就会把你绕晕。所以我们才将这种工作交由计算机来处理。递归本身是帮助我们减轻思维负担的,结果因为一些「程序员思维」的坏处,反而没有享受到这种好处。

想要更有效的使用递归,你必须建立一种思想:在求解一个大问题的时候,想象它分割成的小问题已经解决了。在其小问题已经解决情况下,大问题能不能解决才是我们需要考虑的。如果能够解决,那直接按照上面的步骤,写出递归逻辑即可,而不用再给自己找麻烦了。

这种思维看起来是在自己骗自己,但其实是一种更高阶的抽象思维。站在全局的角度看问题,而不是死磕一个细节,可能也正是大部分程序员需要改正的地方吧。