递归（Recursive）_递归的三要素

1. 递归的三要素

递归的三要素：

1. Base case（递归出口）。可以把 base case 看成是最简单的函数输入情况，或则是递归终止条件。
2. Recursive call on a smaller problem（递归调用一个较小的问题）。我们可以将此步骤视为对当前问题所依赖的较小问题调用函数（分治）。假设对这个小问题的递归调用会给预期的结果，这种想法称为“信念的递归飞跃”（recursive leap of faith）。
3. Solve the larger problem。在步骤2中，我们找到了一个较小问题的结果。我们现在想要使用这个结果来计算当前问题的结果应该是什么，这就是我们想要从当前函数调用中返回的结果。

在处理或调试递归函数时，应该避免以这种方式对大型或复杂的输入进行可视化，因为大量的 frame 可能相当笨拙和令人困惑。相反，应当考虑以下三个步骤:基本情况、递归调用和解决完整问题（base case, recursive call, and solving the full problem）。

2. 什么时候加辅助函数（helper function）

辅助函数（helper function）是一种嵌套函数（nested function），如果需要跟踪给定参数以外的更多变量，或者需要更改输入的值，就很有用。

以 is_prime(n)为例。使用 while 的解法：

def is_prime(n): 
	"""
	>>> is_prime(10) 
	False 
	>>> is_prime(7) 
	True 
	>>> is_prime(1) # one is not a prime number!! 
	False 
	""" 
	if n == 1: 
		return False
	k = 2 
	while k < n: 
		if n % k == 0: 
			return False
	k += 1
	return True
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
'
运行
运行

使用递归：

def is_prime(n):
    """ Returns True if n is a pirme number and False otherwise
    >>> is_prime(2)
    True
    >>> is_prime(16)
    False
    >>> is_prime(521)
    True
    """
    def prime_helper(m):
        if m == n:
            return True
        elif n % m == 0:
            return False
        else:
            return prime_helper(m + 1)
    return prime_helper(2)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
'
运行
运行

如果只用 n 来记录函数的状态是不够的。很明显，在 while 版本中，我们需要跟踪 n 和 k 的改变，如果 k = n，迭代就结束。

如果想要用递归来解决，最起码需要两个参数来记录函数的状态。本例是 m 和 n。
接下来就分析出问题的 base case，以及如何分解问题为更小的子问题，最后再将结果整合。