本章内容
- 学习递归-一种优雅的问题解决方法
- 学习如何将问题分成基线条件和递归条件
递归
- 伪代码:伪代码是对手问题的简要描述,看着像代码,但其实更接近自然语言。
- 递归只是让解决方案更清晰,并没有性能上的优势。有些情况下,使用循环的性能更好。正如《Stack Overfloe》上说的:‘如果使用循环,程序的性能可能会更高;如果使用递归,程序可能更容易理解,如何选择要看什么对你来说更重要。’
基线条件和递归条件
编写函数时,必须告诉它何时停止调用。正因为如此,每个递归函数都有两个部分:基线条件(base case)和递归条件(recursive case)。递归条件指的是函数调用自己,而基线条件是函数不再调用自己,从而避免无限循环。
例如,编写一个倒计时函数:
def countdown(i):
print(i)
return countdown(i-1)
print(countdown(9))
这样编写程序会一直倒数下去,我们需要添加基线条件告诉函数何时停止递归。
def countdown(i):
print(i)
if i <= 1: #基线条件:递归退出的条件
return
else: #递归条件
return countdown(i - 1)
栈
- 栈是一种特殊的列表,栈内的元素只能通过列表的一端访问,这一端称为栈顶。咖啡厅内的一摞盘子是现实世界中常见的栈的例子。只能从最上面取盘子,盘子洗净后,也只能摞在这一摞盘子的最上面。栈被称为一种后入先出(LIFO,last-in-first-out)的数据结构。
- 由于栈具有后入先出的特点,所以任何不在栈顶的元素都无法访问。为了得到栈底的元素,必须先拿掉上面的元素。
- 对栈的两种主要操作是将一个元素压入栈和将一个元素弹出栈。入栈使用push()方法,出栈使用pop()方法。下图演示了入栈和出栈的过程。
- 一个常用的操作是预览栈顶的元素。pop()方法虽然可以访问栈顶的元素,但是调用该方法后,栈顶元素也从栈中被永久性地删除了。peek()方法则只返回栈顶元素,而不删除它。
- 为了记录栈顶元素的位置,同时也为了标记哪里可以加入新元素,我们使用变量top,当向栈内压入元素时,该变量增大;从栈内弹出元素时,该变量减小。push()、pop()和peek()是栈的3个主要方法,但是栈还有其他方法和属性,如下表:
Stack() | 建立一个空的栈对象 |
push() | 把一个元素添加到栈的最顶层 |
pop() | 删除栈最顶层的元素,并返回这个元素 |
peek() | 返回最顶层的元素,并不删除它 |
isEmpty() | 判断栈是否为空 |
size() | 返回栈中元素的个数 |
其中:push()、pop()和peek()是栈的3个主要方法。
操作示例:
操作 | 描述 |
---|---|
s = [] | 创建一个栈 |
s.append(x) | 往栈内添加一个元素 |
s.pop() | 在栈内删除一个元素 |
not s | 判断是否为空栈 |
len(s) | 获取栈内元素的数量 |
s[-1] | 获取栈顶的元素 |
使用Python中的列表对象:
class Stack:
"""模拟栈"""
def __init__(self):
self.items = []
def isEmpty(self):
return len(self.items)==0
def push(self, item):
self.items.append(item)
def pop(self):
return self.items.pop()
def peek(self):
if not self.isEmpty():
return self.items[len(self.items)-1]
def size(self):
return len(self.items)
调用栈(call stack)
调用栈(call stack)是重要的编程概念,使用递归也必须理解这个概念。
简单例子:
def greet(name):
print('Hello '+name+'!')
greet2(name)
print('getting ready to say bye...')
bye()
def greet2(name):
print('How are you '+name+'?')
def bye():
print('ok!bye')
print(greet('kanghaov'))
t('Kanghaov'))
结果:
Hello kanghaov!
How are you kanghaov?
getting ready to say bye...
ok!bye
None
代码中可以看到当调用greet('kanghaov')时,计算机会为该函数分配一块内存,变量name被设置为kanghaov。接下来打印Hello kanghaov时,再调用greet2('kanghaov'),并同样的分配它一块内存。
计算机使用一个栈来表示这些内存块,其中第二快内存块位于第一块内存块的上面,当打印完:How are you kanghaov?,greet2()(位于栈顶)就被弹出。此时栈顶的内存为函数greet(),意味着我们返回到了函数greet(),这是非常重要的:调用另一个函数时,当前函数暂停并处于未完成状态。该函数说有变量的值都还在内存中。接着函数往下执行bye()函数,使用后被弹出,返回到greet()函数,结束。
这个栈用于存储多个函数的变量,被称为调用栈
递归调用栈
递归函数
def fact(x):
if x == 1:
return x
else:
return x * fact(x-1)
每个栈都有自己的变量x。在同一个函数调用中不能访问另一个x的变量。
总结
- 递归指的是调用自己的函数
- 每个递归函数都有两个条件:基线条件、递归条件
- 栈有两种操作:压入和弹出
- 所有函数调用都进入调用栈
- 调用栈可能很长,这将占用大量内存。
发表回复