《算法图解》第三章选择排序
第三章 递归
1.递归的思想
是调用自己的函数
2.递归和循环
如果使用循环,程序的性能可能更高,如果使用递归,可能更容易理解,阶数,5!
def fact(x):
if x==1:
return
else x*fact(x-1)
3.基线条件和递归条件
每个递归函数分为两部分,基线条件和回归条件,基线条件是避免循环不停止(无限循环),不调用递归函数了,递归函数是调用函数本身
def count(i):
print(i)
count(i-1)
该程序不会停下来
def count(i):
print(i)
if i==0:【基线条件】
return
else count(i-1)【递归条件】
4.栈
4.1调用栈
4.2递归调用栈
def fact(x):
if x==1:
return
else x*fact(x-1)
注意:每个fact都调用自己的x变量,不能调用其他的fact的x变量??
5.栈的缺点
存储详尽的信息可能占据大量内存,每个函数调用都占用一定的内存,如果栈很高,则说明计算机存储了很多栈的调用内容
在这种情况
下,你有两种选择。
重新编写代码,转而使用循环。
使用尾递归。这是一个高级递归主题,不在本书的讨论范围内。另外,并非所有的语言
都支持尾递归。
6.小结
递归指的是调用自己的函数。 每个递归函数都有两个条件:基线条件和递归条件。
栈有两种操作:压入和弹出。
所有函数调用都进入调用栈。
调用栈可能很长,这将占用大量的内存。