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

小鱼儿 2022-01-20 00:23 232阅读 0赞

### 递归 ###

--------------------

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

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

### 基线条件和递归条件 ###

--------------------

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

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执行完毕，出栈
    复制代码

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

### 递归调用栈 ###

--------------------

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

### 小结 ###

--------------------

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