小白的算法初识课堂(part3)--递归

学习笔记
学习书目：《算法图解》- Aditya Bhargava

---

---

递归

首先，我们看一段代码：

def print_num(my_list):
    for i in my_list:
        print(i)

print_num([1, 3, 5, 7, 9])

输出：

1
3
5
7
9

再看一段代码：

def print_num2(my_list):
    if my_list:
        print(my_list.pop(0))
        print_num2(my_list)
        
print_num2([1, 3, 5, 7, 9])

输出：

1
3
5
7
9

我们看到的第一段代码使用的是循环，第二段代码使用的是递归，两种方法结果相同。一般来说，递归能让解决方案更清晰(虽然我举的例子好像没体现出来递归法更清晰)，但并没有性能上的优势。实际上，在有些情况下，使用循环的性能更好。

如果使用循环，程序的性能可能更高；如果使用递归，程序可能更容易理解。如何选择要看什么对你来说更重要。

基线条件和递归条件

由于递归函数调用自己，因此编写这样的函数时很容易出错，进而导致无限循环。例如，假设我要编写一个像下面这样倒计时的函数：

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

如果我们运行上述代码，将发现一个问题：这个函数运行起来没完没了！

编写递归函数时，必须告诉它何时停止递归。正因为如此，每个递归函数都有两部分：基线条件（base case）和递归条件（recursive case）。递归条件指的是函数调用自己，而基线条件则指的是函数不再调用自己，从而避免形成无限循环。

我们来给countdown函数添加一个基线条件：

def countdown(i): 
    print(i)
    if i <= 1:
        return
    else:
        countdown(i-1)

现在，这个函数就会像预期那样运行.

栈

假设我们有一叠便条，这叠便条记录着我们马上要做的待办事项，我们简称这叠便条为清单。当我们插入的待办事项时，这个事件会放在清单的最上面；当我们读取待办事项时，也只读取清单最上面的那个，且读完就将其销毁。因此这个清单只有两种操作：压入（插入）和弹出（删除并读取）。

这种数据结构被称为栈。

调用栈

计算机在内部使用被称为调用栈的栈。

为了演示计算机是如何调用栈的，我们来看下面这个简单的函数：

def greet(name):
    print(name, '!')
    greet2(name)
    print('too late!')
    bye()

def greet2(name):
    print(name, '?')

def bye():
    print('bye!')

greet('maggie')

注意！print是一个函数，但是出于简化考虑，我们假设它不是函数。

假设，我们调用greet('maggie')，计算机将首先为该函数调用分配一块内存空间：

变量name被赋值为maggie，这需要存储到内存中：

当我们调用函数时，计算机会将函数调用涉及的所有变量的值存储到内存中。接下来，我们再调用greet2('maggie').同样，计算机也为这个函数调用分配一块内存。

计算机使用一个栈来表示这些内存块，其中第二个内存块位于第一个内存块上面。我们打印maggie ?，然后从函数greet2的调用返回。此时，栈顶的内存块被弹出。

现在，栈顶的内存块是函数greet的，这意味着我们返回到了函数greet。当我调用函数greet2时，函数greet只执行了一部分。调用另一个函数时，当前函数暂停并处于未完成状态，该函数的所有变量的值仍在内存中。

当执行完greet2函数后，我们继续向下执行，首先打印too late!，再调用函数bye()。计算机在栈顶添加了函数bye的内存块，然后我们打印bye!，并从该函数中返回。

现在，我们又回到了greet函数，由于无事可做，我们就从greet函数中返回。这个栈用于存储多个函数的变量，故被称为调用栈。

递归调用栈

递归函数也使用调用栈，我们来看看下面这个递归函数fact：

def fact(x):
    if x == 1:
        return 1
    else:
        return x*fact(x-1)

print(fact(3)) 

输出：

6

下面我们来看一下调用fact(3)时，调用栈的变化：

每个fact调用都有自己的x变量，在一个函数调用中不能访问另一个函数的x变量。