Python理解递归的方法总结

递归

一个函数在执行过程中一次或多次调用其本身便是递归，就像是俄罗斯套娃一样，一个娃娃里包含另一个娃娃。

递归其实是程序设计语言学习过程中很快就会接触到的东西，但有关递归的理解可能还会有一些遗漏，下面对此方面进行更加深入的理解

递归的分类

这里根据递归调用的数量分为线性递归、二路递归与多重递归

线性递归

如果一个递归调用最多开始一个其他递归调用，我们称之为线性递归。

例如：

def binary_search(data, target, low, high):  """  二分查找，对有序列表进行查找，如果找到则返回True，否则返回False   """   if low > high:    return False  else:    mid = (low + high) // 2    if target == data[mid]:      return True    elif target < data[mid]:      return binary_search(data, target, low, mid - 1)    else:      return binary_search(data, target, mid + 1, high)

虽然在代码中有两个binary_search，但他们是不同条件执行的，每次只能执行一次，所以是线性递归。

二路递归

如果一个递归调用可以开始两个其他递归调用，我们称之为二路递归

例如：

def binary_sum(S, start, stop):  """  二路递归计算一个序列的和，例如S[0:5],就像切片的范围一样   """   if start >= stop:    return 0  elif start == stop - 1:    return S[start]  else:    mid = (start + stop) // 2    return binary_sum(S, start, mid) + binary_sum(S, mid, stop)

这个递归每次执行都会调用两次该函数，所以说是二路递归，每次递归后，范围缩小一半，所以该递归的深度是1+logn

多重递归

如果一个递归调用可以开始三个或者更多其他递归调用，我们称之为多重递归

例如：

import os def disk_usage(path):  """  计算一个文件系统的磁盘使用情况，   """   total = os.path.getsize(path)  if os.path.isdir(path):    for filename in os.listdir(path):      childpath = os.path.join(path, filename)      total += disk_usage(childpath)  print('{0:<7}'.format(total), path)  return total

os.path.getsize为获得标识的文件或者目录使用的即时磁盘空间大小。我理解的是如果该标识的是一个文件，那么就是获得该文件的大小，如果是一个文件夹的话，那就是获得该文件夹的大小，但不包括文件夹里边的内容，就像是一个盒子中放了很多物品，但这里只计算了盒子的重量，但没有计算物品的重量，也就是计算了一个空盒子。所以这个递归函数中的递归调用次数取决于这一层文件或文件夹的数量，所以是多重递归。

递归的不足

递归的不足显然就是时间与空间的消耗 ，这篇文章中使用了缓存的方法减少了斐波那契数列的计算消耗，在这里我们使用另一种方式来改善那种坏的递归：