Nemo
Nemo
《算法图解》-第三章:递归和栈
《算法图解》-第三章:递归和栈

本章内容

  • 学习递归-一种优雅的问题解决方法
  • 学习如何将问题分成基线条件和递归条件

TOC


递归

  • 伪代码:伪代码是对手问题的简要描述,看着像代码,但其实更接近自然语言。
  • 递归只是让解决方案更清晰,并没有性能上的优势。有些情况下,使用循环的性能更好。正如《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()方法。下图演示了入栈和出栈的过程。
    https://essay-1256185664.cos.ap-guangzhou.myqcloud.com/%E5%8D%9A%E6%96%87%E9%85%8D%E5%9B%BE/%E7%AE%97%E6%B3%95%E7%B1%BB%E9%85%8D%E5%9B%BE/3bf1b51d-4582-4586-ba69-4d0e524040a5.jpg
  • 一个常用的操作是预览栈顶的元素。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的变量。

总结

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

Nemo版权所有丨如未注明,均为原创丨本网站采用BY-NC-SA协议进行授权,转载请注明转自:https://kanghaov.com/155.html
https://secure.gravatar.com/avatar/9fd8359b8faa6f7789f9623ba6041e4a?s=256&d=identicon&r=g

kanghaov

文章作者

推荐文章

发表评论

textsms
account_circle
email

Nemo

《算法图解》-第三章:递归和栈
本章内容 学习递归-一种优雅的问题解决方法 学习如何将问题分成基线条件和递归条件 本章内容递归基线条件和递归条件栈调用栈(call stack)递归调用栈总结TOC 递归 伪代码:伪代码…
扫描二维码继续阅读
2019-06-04