【算法图解】读书笔记:第3章 递归

2,124 阅读2分钟

递归


在我看来,递归就类似俄罗斯套娃,一次次重复去执行相同的操作,最后得出结果的过程。

很多递归的操作都可以使用循环来替代。递归并没有带来算法性能上的优势,甚至更差,但是使用递归可能让你的程序更易理解。所以理解递归这种概念很重要。

基线条件和递归条件


由于递归函数调用自己,很容易导致无线循环。比如,你需要一个倒数的函数:

def countdown(i):
  print(i)
  countdown(i - 1)

countdown(3)

如果运行上述代码,这个函数就会不停的运行。

编写递归函数式,必须告诉它何时停止递归,

每个递归函数都有两部分:基线条件(base case)和递归条件(recursive case)。递归条件指的是函数调用自己,而基线条件则 指的是函数不再调用自己,从而避免形成无限循环。

好了,我们尝试为上面的代码增加基线条件:

def countdown(i):
  print(i)
  if i <= 0: # 基线条件
    return
  else: # 递归条件
    countdown(i - 1)

countdown(3)
# 3 2 1 0 程序停止


调用栈不仅对于编程来说很重要,使用递归是也必须裂解这个概念。计算机在内部使用被称为调用栈的栈。

我们简单看一个例子:

# 忽略 print 这个函数带来的影响
# 开始执行函数 greet ,此时内存中开辟一块空间 greet 进入栈中
def greet(name):
  # 在 greet 的内存中,添加变量name
  print "hello, " + name + "!"
  # 开始执行 greet2 ,此时内存中开辟空间 greet2,greet2 入栈
  # greet <-- greet2 类似这种链式结构
  greet2(name)
  # greet2 执行完毕,出栈
  # greet
  print "getting ready to say bye..." 
  # 开始执行bye ,此时内存中开辟空间 bye,bye 入栈
  # greet <-- bye
  bye()
  # bye 执行完毕,出栈
  # greet
# 最后greet执行完毕,出栈

栈的执行逻辑就是:先进后出原则。

递归调用栈


递归调用中,存储详尽的信息可能占用大量的内存。这回付出很大的代价。如果占用过高,你需要使用循环去代替递归,或者使用尾递归优化,前提是你的语言支持尾递归优化。

小结


  • 递归指的是调用自己的函数。
  • 每个递归函数都有两个条件:基线条件和递归条件。
  • 栈有两种操作:压入和弹出。
  • 所有函数调用都进入调用栈。
  • 调用栈可能很长,这将占用大量的内存