理解递归

从前有座山，山里有座庙，庙里有个老和尚，正在给小和尚讲故事呢！故事是什么呢？“从前有座山，山里有座庙，庙里有个老和尚，正在给小和尚讲故事呢！故事是什么呢？‘从前有座山，山里有座庙，庙里有个老和尚，正在给小和尚讲故事呢！故事是什么呢？……’”

读完这段话你是否有一种晕头转向的感觉? 或许你已经发现其中的一些端倪。 这是一种层层嵌套和结构相似的形式，在数学和计算机领域把这种形式叫做「递归」。

除此之外在生活中也有很多「递归」的存在，比如查字典的过程：遇到一个生词 "xx" 找一本字典查找定义，但是在定义又遇到了生词 "yy1", "yy2" , 因此我们继续查找生词 "yy1", "yy2" 的定义，直到所有的定义中不出现生词为止。

神奇的贝壳,花菜的纹络符合斐波纳契数(Fibonacci),排列形成一种螺旋式结构,这也是一种递归的形式。

Fibonacci Fibonacci

递归是一种解决复杂编程问题的有效方法，在计算机领域有着极其广泛的应用。其特点是表达形式简洁优雅，一开始理解起来却非常困难，需要通过大量的练习，反复思考才能掌握递归的精髓。

定义

---

递归 (recursion )是一个函数定义中调用函数本身。通常用于把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解，递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。

一个例子

---

双倍

双倍问题:

假设有一碗M&M糖，我们不知道有多少颗糖在碗中 ，通过不用数数字的方法来增加一倍糖的数量，也就是说把糖的数量变成原来的两倍。

前提条件：

1： 有一群人，人数超过糖的数量一起来完成这个任务。
2： 旁边有一麻袋的M&M糖可供使用，数量远远超过一碗M&M糖。

如果可以一个一个得数，解决这个问题的方法显而易见，先数出糖的数量，然后从旁边的麻袋中拿出同等数量即可。但是不能用这个方法，我们就要换一个思路来解决这个问题。

暂停几分钟，认真思考一下这个问题。

解决方法是: 把这群人排个队，然后告诉每个人记住一个规则。

双倍糖数量规则:
如果 碗中 没有 糖了，把碗传递给之前那个人。
否则的话，从碗中取出一颗糖，然后传递给队伍中后一个人，告诉他使用这个 双倍糖数量规则。
当碗传回来的时候，放入2颗糖当碗中，然后把碗传给队伍中前一个人。

示意图

以上示意图假设碗中只有4颗糖，通过一个分工合作的流程， 碗从左往右传递时候每个人取出碗中的一颗糖，当碗空了以后，把碗传递回来每个人把原来的那颗糖放回碗中，并且从麻袋中取一颗糖再放入碗中。 我们可以看到，每个人递归使用一个简单的规则，即使人不会数数也可以完成双倍的任务。

通过以上例子，相信应该能加深对递归的认识。

递归使用

---

递归实际上是通过将一个大的问题不断地分解成规模更小的子问题，并且大问题和小问题的解决方法是一样的。直到归约成一个可以直接得到子答案问题，然后返回合并得到计算结果。

在实际开发中，递归程序有一个通用的格式， 分别处理两种情况:

1. 基准情况(Base Case)，也称递归基。
   有效递归定义的关键是具有终止条件，使得到达某一点后不再递归，否则会导致无穷递归。

2. 递归情况, 不能直接返回结果，需要依赖次一级的递归调用才能得出计算结果。

例如 求阶乘的例子:

def factorial(n):
    if n == 0: #递归基
        return 1
    else:
        return n * factorial(n-1) #递归情况

递归练习

---

0. 如何逆向显示一个 嵌套结构的列表？

[1,[2,3],4,[5,6,[7,8],9]]

def reverse_list(alist):
    if  alist    != []:
        reverse_list(alist[1:])
        if  type(alist[0]) == list:
            reverse_list(alist[0])
        else:
            print(alist[0],end="   ")
      
    
list1  =  [1,[2,3],4,[5,6,[7,8],9]]
reverse_list(list1)

[out]: 9  8  7  6  5  4  3  2  1 

1. 判断一个字符串是否是回文（左右对称的字符串）。

如：
“Java” -> False
“madam” -> True
“Q” -> True
"byebye" -> False

def isPalindrome(astr):
    if len(astr)<=1:
        return True
    else:
       return   (astr[0]   ==  astr[-1]) and isPalindrome(astr[1:-1])


isPalindrome('madam')
[out]: True
isPalindrome('Java')
[out]: False

2. 文件内容翻转

file_content   =  '''
Roses are red,
Violets are blue,
Sugar is sweet,
And so are you.
'''.split(',')

def flip(pm):
    if len(pm)<=1:
        return pm
    else:
        #swap head tail  
        return [pm[-1]]+flip(pm[1:-1])+[pm[0]]
flip(poem)  
 
[out]: ['And so are you.',
 'Sugar is sweet',
 'Violets are blue',
 'Roses are red']

3. 打印一个整数的二进制形式

def print_binary(n):
    if n < 0 :
        print("-", end='')
        print_binary(-n)
    elif   n ==    0 or n    ==1:
        print(int(n), end='')
    else:
        last   =   n   % 2
        rest =  int(n / 2)
        
        if rest > 0:
            print_binary(rest)
        print(last, end='')
        
 
print_binary(5)   
[out]: 101

4.Hanoi 塔问题是用递归求解的经典案例。

将 n 个圆 盘从 A 柱移到 C 柱，移动过程中可以利用 B 柱作为临时存放柱。
具体的移动圆盘的规则是：

1. 圆盘只能放在柱子上；
2. 每次只能移动位于任一柱子顶部的圆盘；
3. 大圆盘永远不能置于小圆盘之上；

核心解法是：

利用第三个柱子作为临时存放点，把 n-1个盘先移动到临时存放点，然后把最大的盘子移动到目标柱子，直到只剩下一个盘子的情况直接把盘子从源柱子移动到目标柱子。

初始状态 递归缩小规模

这个思路使用递归来表达非常方便。

def  hanoi(n,source,target,temp):
    if n == 1:
        print("{0}  {1} -> {2} ".format(1, source,target))
    else:
        #   move   n-1  to  temp
        hanoi(n-1,source,temp,target)
        # move  n  to  target 
        print("{0}  {1} -> {2} ".format(n, source,target))
        #move n-1 to target
        hanoi(n-1,temp,target,source)
        
hanoi(3,"A","C","B")

'''
[out]: 
1  A -> C 
2  A -> B 
1  C -> B 
3  A -> C 
1  B -> A 
2  B -> C 
1  A -> C 

最后

---

递归是一种强大的算法设计思想，利用递归可以轻松解决很多难题。
虽然递归算法容易设计实现，也容易理解，但递归是有代价的。由于递归涉及大量的函数调用，因此需要耗费较多的内存和较长的执行时间，过多的递归调用导致程序出现stackoverflow栈溢出 异常, 一般可以通过循环(while ,foor-loop)来优化。

参考

1: CS 106B
2: 维基百科