Pythonにおける再帰

プログラミングには、再帰という概念があります - 関数が自分自身を呼び出す場合です。

例 . カウンターを用いた単純な再帰

再帰を使って、 1から10までの数字を出力してみましょう:

i = 1

def func():
	global i
	print(i)
	i += 1

	if i <= 10:
		func() # ここで関数が自分自身を呼び出します

func()

このコードがどのように動作するか説明しましょう。

グローバル変数iと関数funcがあります。関数の内部では、変数iの内容がコンソールに出力され、その後1が加算されます。

変数iが10以下の場合、関数は再度呼び出されます。変数iがグローバル変数であるため、関数が呼び出されるたびに、前回の呼び出しで設定された変数iの値が使用されます。

結果として、関数はiが10を超えるまで自分自身を呼び出し続けます。

この場合、ifなしで関数を起動することはできません - もしそうすると、関数の無限呼び出しが発生します。

例 . ネストされたリストの要素を出力するための再帰

再帰は、さまざまなレベルのネストを持つリストを走査するためによく使用されます。次のリストがあるとします:

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

このリストを走査する関数を作成してみましょう。まず、プリミティブ（リストから単純に取り出された数値）である要素がコンソールに出力されるように条件を設定する必要があります。要素がオブジェクト（例えばネストされたリスト）である場合、関数が自分自身を呼び出すようにします。つまり、再帰が発生します。要素の型をチェックするためにisinstance関数を使用します。この例では、isinstanceの最初のパラメーターに elを、2番目のパラメーターに型listを記述します:

def func(lst):
	for el in lst:
		if isinstance(el, list):
			func(el)
		else:
			print(el)

関数を呼び出すと、ネストされたリストからすべての数値が順番に出力されます:

func(lst) # 1, 2, ... 8, 9 を出力します

例 . ネストされたリストの要素に対する操作のための再帰

再帰は、ネストされたリストの要素に対するさまざまな操作にも使用できます。次のリストがあるとします:

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

すべての要素の合計を求めてみましょう。そのために関数内に、数値の合計を累積する変数resを宣言します。条件として、要素が複雑なオブジェクト（リスト）である場合、関数funcのパラメーターに入り、合計に加算されるように記述します。これは、要素がプリミティブになるまで再帰処理されることを意味します。その場合、単純にresに記録された合計に加算されます:

def func(lst):
	res = 0
	for el in lst:
		if isinstance(el, list):
			res += func(el)
		else:
			res += el
	return res

関数を呼び出し、その結果をコンソールに出力してみましょう:

print(func(lst)) # 45 を出力します

例 . リストへの累積のための再帰

再帰を使用して、ネストされたリストを1つの一次元リストに展開することができます。次のリストがあるとします:

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

関数内に、元のリストの要素を累積するための空のリスト resを記述します。次にループを開始し、条件を設定します - 要素がリストの場合、メソッドextendに入ります。このメソッドは、あるリストの要素を別のリストの末尾に結合します。つまり、ネストされたリストの要素がリスト resの末尾に入ります:

def func(lst):
	res = []
	for el in lst:
		if isinstance(el, list):
			res.extend(func(el))
		else:
			res.append(el)
	return res

print(func(lst))

実行されたコードの結果:

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

実践的なタスク

任意のレベルのネストを持つ辞書のすべての数値要素を出力してください:

{
	'a': {
		'b': 1,
		'c': 2,
		'd': {
			'e': 3,
			'f': 4
		}
	},
	'j': {
		'h': 5,
		'k': 6,
	},
	'l': 7
}

前のタスクの辞書の要素の合計を求めてください。

前のタスクの辞書のプリミティブ要素のリストを取得してください。