Python 递归的多种写法

全栈程序员-用户IM • 2022年6月16日下午6:46 • 未分类

大家好，又见面了，我是你们的朋友全栈君。

题目背景：

让我们来看一些例子。要对一个数字列表（或者其他序列）求和，我们可以使用内置的sum函数，或者自己编写一个更加定制化的版本。这里是用递归编写的一个定制求和函数的示例

def mysum(L):
	if not L:
		return 0
	else:
		return L[0] + mysum(L[1:])

这是一种最基本的递归写法，通过递归的方式将列表中的所有进行相加，典型的鸭子类型。

编码替代方案：

有趣的是，我们也可以使用Python的三元if/else表达式。我们也可以针对任何可加和的类型一般化（如果我们至少假设输入中的一项的话，这将会变得较容易些，就像我们在第18章最小最大值的示例中所做的那样），并且使用Python 3.0的扩展序列赋值来使得第一个/其他的解包更简单：

def mysum(L):
	return 0 if not L else L[0] + mysum(L[1:]) # 使用三元表达式

def mysum(L):
	return L[0] if len(L) == 1 else L[0] + mysum(L[1:]) # 也是三元表达式，但是不适用[]

def musum(L):
	first, *rest = L
	return first if not rest else first + mysum(rest)

后两者在一个单个字符串参数上也有效（例如，mysum （‘spam’）），因为字符串是一字符的字符串的序列；第三种变体在任意可迭代对象上都有效，包括打开的输入文件，但是，其他的两种不会有效，因为它们索引；并且函数头部def mysum（first, rest）尽管类似于第三种变体，但根本没法工作，因为它期待单个参数，而不是一个单独的可迭代对象。

处理非线性结构的方法

计算一个嵌套的字列表结构中所有数字的总和：

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

解：简单的循环语句在这里不起作用，因为这不是一个线性迭代。嵌套的循环语句也不够用，因为子列表可能嵌套到任意的深度并且以任意的形式嵌套。相反，下面的代码使用递归来对应这种一般性的嵌套，以便顺序访问子列表。

def sumtree(L):
	tot = 0
	for x in L:
		if not isinstance(x, list):
			tot += x
		else:
			tot += sumtree(x)
	return tot
""" print(sumtree(L)) [1, 2, [3, 4], 5, [6, 7, [8, 9]]] [3, 4] [6, 7, [8, 9]] [8, 9] 45 """