Pythonにおける再帰

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

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

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

pythoni = 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なしで関数を起動することはできません - もしそうすると、関数の無限呼び出しが発生します。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

print(func(lst))

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

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

実践的なタスク

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