个人作品网站怎么做,江阴网站开发,做的好的宠物食品网站,新媒体ui设计是干什么的数据结构和算法 基于《算法图解》—Aditya Bhargava和《数据结构》—严蔚敏
第3章 递归
3.1 递归 假设在一堆嵌套的盒子里找钥匙#xff0c;对比循环和递归。 使用循环解决#xff1a;
#使用while循环#xff1a;只要盒子堆不是空#xff0c;就从中取出一个盒子#x…数据结构和算法 基于《算法图解》—Aditya Bhargava和《数据结构》—严蔚敏
第3章 递归
3.1 递归 假设在一堆嵌套的盒子里找钥匙对比循环和递归。 使用循环解决
#使用while循环只要盒子堆不是空就从中取出一个盒子并在其中仔细查找。
def look_for_key(main_box):pile main_box.make_a_pile_to_look_through()while pile is not empty:box pile.grab_a_box()for item in box:if item.is_a_box():pile.append(item)elif item.is_a_key():print(found the key!)使用递归解决
#使用递归函数调用自己
def look_for_key(box):for item in box:if item.is_a_box():look_for_key(item) #递归elif item.is_a_key():print(found the key!)两种办法的作用相同但递归可以让解决方案更清晰并没有性能上的优势使用循环的性能更好。
3.2 基线条件和递归条件
编写递归函数时必须告诉它何时停止递归否则会进入无限循环。每个递归函数都有两部分基线条件(base case)和递归条件(recursive case)。递归条件指的是函数调用自己。基线条件指的是函数不再调用自己避免形成无限循环。 #倒计时函数
def countdown(i):print i if i 1:return #基线条件else:countdown(i-1) #递归条件3.3 栈 栈是一种简单的数据结构。具有两种操作压入(插入)和弹出(读取并删除)。 3.3.1 调用栈(call stack) 用于存储多个函数的变量。
#定义问候函数
def greet(name):print(Hello, name !)#在greet函数内调用另外两个函数greet2(name)print(getting ready to say bye...)bye()
def greet2(name):print(how are you, name ?)
def bye():print(ok bye!)计算机为每个函数调用分配一个内存块并使用一个栈来表示这些内存块其中第二个内存块位于第一个内存块上面栈顶函数调用返回后内存块被弹出。
当我们调用函数greet2时函数greet只执行了一部分调用另一个函数时当前函数暂时并处于未完成状态该函数的所有变量的值都还在内存中执行完函数greet2后回到函数greet并从暂时离开的地方开始接着往下执行。
3.3.2 递归调用栈
#阶乘
def fact(x):if x 1:return 1else:return x * fact(x-1)每个fact调用都有自己的x变量。在一个函数调用中不能访问另一个的x变量。
3.3.3 使用栈的代价 使用栈虽然方便但存储详尽的信息可能占用大量的内存。每个函数调用都要占用一定的内存如果栈很高就意味着计算机存储了大量函数调用的信息。
3.4 小结
递归指的是调用自己的函数。每个递归函数都有两个条件基线条件和递归条件。栈有两种操作压入和弹出。所有函数调用都进入调用栈。调用栈可能很长这将占用大量的内存。
——持续修改完善中…
