关于递归的学习

递归是一种优雅的问题解决方法，同循环相比，并没有性能优势，而是让解决方案更清晰，让程序更容易理解。

递归条件:recursive case

函数调用自己。

基线条件:base case

函数不再调用自己，避免无限循环。

栈

需要用到一种数据结构-栈(stack),一叠数据,操作有两种，分别是：压入和弹出(删除和读取)。

计算机调用函数需要分配一块内存，当调用另一个函数时，当前函数暂停并处于未完成状态，变量也存储于其中。所以也会由于内存不足而导致栈溢出。

递归式解决问题

分而治之(dvide and conquer)的思想

递归式解决问题的方法。

• D&C原理：
  1.找出基线条件；
  2.确定如何缩小问题规模，也能符合基线条件。

问题练习

递归练习题

'''列表求和'''
def Sum(arr):
    n = len(arr)
    print('列表长度为:'+str(n))
    print('当前列表：'+str(arr))
    print('列表第一个元素：'+str(arr[0]))
    print('--'*10)
    if len(arr)==1:
        #这一步通常会被忽略，基线条件达到以后，会返回一个值
        print('完成基线条件的返回值：'+str(arr[0]))
        return arr[0]
    return arr.pop(0)+Sum(arr)

运行结果如下：

>>>Sum([9,13,2,4,67,211,32])
列表长度为:7
当前列表：[9, 13, 2, 4, 67, 211, 32]
列表第一个元素：9
--------------------
列表长度为:6
当前列表：[13, 2, 4, 67, 211, 32]
列表第一个元素：13
--------------------
列表长度为:5
当前列表：[2, 4, 67, 211, 32]
列表第一个元素：2
--------------------
列表长度为:4
当前列表：[4, 67, 211, 32]
列表第一个元素：4
--------------------
列表长度为:3
当前列表：[67, 211, 32]
列表第一个元素：67
--------------------
列表长度为:2
当前列表：[211, 32]
列表第一个元素：211
--------------------
列表长度为:1
当前列表：[32]
列表第一个元素：32
--------------------
完成基线条件的返回值：32
338

'''计算列表元素个数'''
def Len(arr):
    print('当前列表：'+repr(arr))
    count = 0
    arr.pop()
    print('删除队尾元素后的列表：'+repr(arr))
    count +=1
    if arr ==[]:
        return count
    return count+Len(arr)

结果如下：

>>>Len([1,2,3])
当前列表：[1, 2, 3]
删除队尾元素后的列表：[1, 2]
当前列表：[1, 2]
删除队尾元素后的列表：[1]
当前列表：[1]
删除队尾元素后的列表：[]
3

但是当输入列表为[],会由于arr.pop()方法对象为空而报错。

'''找出列表中最大的数字'''
def findMax(arr):
    max_value = 0
    num =arr.pop()
    if arr ==[]:
        return num
    if max_value<num:
        max_value = num
        print('当前最大值：'+str(max_value))
        return max_value
    return findMax(arr)

>>>findMax([1,2,3,4,5])
当前最大值：5
5

---

书中练习的答案：

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

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

总结：看了书上的解法，真的是优雅，基线条件和递归条件一目了然，思路值得学习。

参考

---

《算法图解》