递归是很多算法都使用的一种编程方法.
如计算 5 的阶乘:
5!=5*4!=5*4*3!=5*4*3*2!=5*4*3*2*1
如果用 factorial(n) 表示阶乘, 那么 factorial(5)=factorial(4)5=factorial(3)45=factorial(2)345=factorial(1)2345.
如此不断的调用执行 factorial(n) 就是递归.
祖母留下一个手提箱, 手提箱的钥匙在一个盒子中, 而这个盒子里又有盒子.
问题: 使用什么算法, 找到钥匙?
方法一:
1. 创建一个要查找的盒子堆
2. 从盒子堆中取出一个盒子, 在里面找
3. 如果找到的是盒子, 就将其加入盒子堆中, 以便以后再查找, 原盒子抛弃; 返回第 2 步
4. 如果找到钥匙, 大功告成, 不再查找
- def look_for_key(main_box):
- pile=main_box."建立一个盒子堆"
- while pile is not empty:
- box = pile.grab_a_box()
- for item in box:
if item. 是盒子:
pile.append(item)
elif item. 是钥匙:
print("钥匙找到了")
方法二:
1. 检查盒子的每样东西
2. 如果是盒子, 就回到第一步
3. 如果是盒子, 就大功告成
- def look_for_key(box):
- for item in box:
if item. 是盒子:
look_for_key(item)
elif item. 是钥匙:
print("钥匙找到了")
这两种方法的作用相同, 但方法二更清晰. 递归只是让解决方案更清晰, 并没有性能上的优势. 实际上, 在有些情况下, 使用循环的性能更好.
某大佬曾经说过:"如果使用循环, 程序的性能可能更高; 如果使用递归, 程序可能更容易理解."
1.2 基线条件和递归条件
由于递归函数调用自己, 因此编写这样的函数时很容易出错, 可能导致死循环.
- # 倒计时
- def countDown(i):
- print(i)
- countDown(i-1)
因此编写递归函数是, 必须告诉他何时停止递归. 因此每个递归函数都有两部分: 基线条件和递归条件. 递归条件指的是函数调用自己, 而基线条件则指的是函数不在调用自己, 从而避免形成死循环.
- def countDown(i):
- print(i)
- if(i<=1): #基线条件
- return
- else: #递归条件
- countDown(i-1)
1.3 栈
3 递归
来源: http://www.bubuko.com/infodetail-3338400.html