《算法图解》读书笔记 第三章 递归

如果使用循环，程序的性能可能更高；如果使用递归，程序可能更容易理解。

基线条件和递归条件

基线条件则指的是函数不再调用自己，从而避免形成无限循环。递归条件指的是函数调用自己。举例如下：

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

栈

栈只有两个操作：压入和弹出。

一个栈帧一般包括函数的返回地址、参数、临时变量等内容。调用栈用于存储多个栈帧，调用函数时会压入该函数的栈帧，函数结束时会弹出栈顶的栈帧。

计算阶乘的递归函数：

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

递归调用时调用栈的变化：

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

使用栈虽然很方便，但是也要付出代价：存储详尽的信息可能占用大量的内存。每个函数调用都要占用一定的内存，如果栈很高，就意味着计算机存储了大量函数调用的信息。在这种情况下，你有两种选择：

• 重新编写代码，转而使用循环。
• 使用尾递归 。这是一个高级递归主题，不在本书的讨论范围内。另外，并非所有的语言都支持尾递归。

小结

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