Python での再帰を理解する: それで、それに直面するつもりですか?

再帰はプログラミングの基本的な概念ですが、少し不思議に思えることもあります。それでは、これを単純化して、思ったよりも簡単であることを見てみましょう!

再帰とは何ですか?

再帰とは、関数がそれ自体を呼び出すことによって問題を解決することです!はい、そうです。それは、何度も繰り返し語られる物語のように機能し、最後に到達するまで毎回少しずつ短くなります。しかし、正しく動作するには、2 つの黄金律を満たす必要があります:

1. 終了条件: これは関数が停止する必要があるポイントです。停止しないと永遠ループに留まります (それは望ましくありませんよね?)。
2. 自己呼び出し: これは関数が自分自身を呼び出すときであり、終了条件に達するまでどんどん深くなっていきます。

それでは、これが実際にどのように機能するかを見てみましょう。

どのように機能するのでしょうか?

これをよりわかりやすく説明するには、階乗の古典的な例に勝るものはありません。 (5!) を計算したいと想像してください (「5 階乗」と読んでください)。どのように機能しますか?

5! = 5 * 4 * 3 * 2 * 1!

しかし、再帰を使用すると、次のように考えることができます:

5! = 5 * 4!

そして、順番に、4! は (4 * 3!) となり、(1!) に達するまで続きます。これが 基本ケース (終了)条件)。

実践例: 階乗

コードに進みましょう。ここでコンセプトが生きてくるからです。これは再帰を使用した有名な階乗計算です:

def fatorial(numero):
    if numero == 0 or numero == 1:
        return 1  # caso base
    else:
        return numero * fatorial(numero - 1)

説明:

1. ここでの基本ケースは、数値が 0 または 1 の場合であり、関数は単に 1 を返します。
2. 数値が 1 より大きい場合、関数は数値 - 1 で呼び出され、基本ケースまでの値が累積されます。

複雑

• 時間: (O(n)) — n 回の再帰呼び出しがあるため。
• スペース: (O(n)) — 実行スタックの深さは n です。

実践例: フィボナッチ

もう 1 つの広く使用されている例は、フィボナッチ数列 です。彼女はこんな感じです:

f(0) = 0、f(1) = 1、f(n) = f(n - 1) f(n - 2)

コードを見てみましょう!

def seq_fib(n):
    if n == 0:
        return 0
    if n == 1:
        return 1
    if n > 1:
        return seq_fib(n - 1) + seq_fib(n - 2)

フィボナッチ複雑度:

• 時間: (O(2^n)) — 指数関数的! ⚠️
• スペース: (O(n)) — 再帰呼び出しのスタック使用量。

そのため、大きな値の場合、純粋な再帰によるフィボナッチ計算は少し面倒になる可能性があります。しかし、学習目的としては、これは素晴らしい例です!

ついに

再帰はプログラミングにおける重要な概念であり、最初は少し怖く思えるかもしれませんが、練習するとずっと簡単になります。これらの階乗とフィボナッチの例はほんの始まりにすぎません。

練習したい場合は、この Colab でチェックしてコピーしてください。

以上がPython での再帰を理解する: それで、それに直面するつもりですか?の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。