递归

Loops may achieve a performance gain for your program. Recursion may achieve a performance gain for your programmer. Choose which is more important in your situation!
使用循环，程序的性能可能更高；使用递归，程序可能更容易理解。如何理解要看什么对你更重要！

引子

宝箱中藏着金钥匙。


盒子套盒子，该如何找钥匙呢？

方法一：使用循环

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!"

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

分而治之（divide and conquer，D&C）

例子

1. 列表求和

循环写法：

def sum(arr):
  total = 0
  for x in arr:
    total += x
  return total

遍历写法：

def sum(list):
  if list == []:
    return 0
  return list[0] + sum(list[1:]

2. 计算列表的元素数

def count(list):
  if list == []:
    return 0
  return 1 + count(list[1:])

3. 找出列表中的最大值

def max(list):
  if len(list) == 2:
    return list[0] if list[0] > list[1] else list[1]
  sub_max = max(list[1:])
  return list[0] if list[0] > sub_max else sub_max