Python再帰関数の概念：初心者向けのPythonチュートリアル

コンピュータサイエンスの世界では、再帰とは、物事を独自の用語で定義する手法を指します。 つまり、再帰関数はそれ自体を呼び出して処理します。 この記事では、21世紀に広く使われているプログラミング言語であるPythonの再帰関数の概念を理解します。

Python再帰とは何ですか？

Pythonでは、特定のタスクを実行する関連ステートメントのグループは「関数」と呼ばれます。 したがって、関数はプログラムを小さなチャンクに分割します。 また、関数がPythonの他の関数を呼び出すことができることは一般的な知識です。

しかし、他のいくつかの関数はそれ自体を呼び出すことができます。 これらは再帰関数として知られています。 向かい合って配置された2つの平行なミラーについて考えてみます。 これで、ミラーの間に保持されているオブジェクトは再帰的に反射されます。

再帰関数について詳しく説明し、その動作を明確に理解しましょう。

再帰関数

Pythonの再帰関数は、自己参照式を介して、つまりそれ自体に関して定義されているため、それ自体を呼び出すことがわかっています。 値または結果を返すために特定の条件が満たされるまで、その動作を繰り返し続けます。 それがどのように機能するかを学ぶために例を見てみましょう。

また読む： Pythonインタビューの質問と回答

整数の階乗を調べたいとします。 階乗は、1からその整数までのすべての数値の積に他なりません。 たとえば、5の階乗（5と表記）は1 * 2 * 3 * 4 * 5 * 6、つまり720になります。再帰関数calc_factorial（x）があり、次のように定義されています。

def calc_factorial（x）：

＃整数の階乗を見つける再帰関数

x == 1の場合：

リターン1

そうしないと

return（x * calc_factorial（x-1））

この関数を4のような正の整数で呼び出すとどうなりますか？ さて、各関数呼び出しは、基本ケースに到達するまで（数が1に減少したとき）、スタックフレームを追加します。 基本条件は、再帰が終了して無期限に継続しないようにするために必要です。 したがって、指定されたケースでは、値24が4回目の呼び出しの後に返されます。

Pythonでの再帰関数の実装

Pythonには、再帰関数のさまざまなアプリケーションがあります。 たとえば、コッホスノーフレークのように、繰り返しパターンのグラフィックを作成したいとします。 再帰は、同じデザインの小さいバージョンで構成されるフラクタルパターンを生成するために使用できます。

もう1つの例は、ゲーム解決の例です。 数独や多数の複雑なゲームを解くための再帰的アルゴリズムを書くことができます。 再帰は、検索、並べ替え、およびトラバーサルの問題で最も一般的に使用されます。

この関数の顕著な特徴は、再帰的な実装によりバックトラックが可能になることです。 したがって、再帰とは、ソリューションを段階的に構築し、どの段階でも問題の制約を満たさないソリューションを削除することです。 これを実現するには、状態の維持と適切なデータ構造の2つが必要です。 これらの用語を理解するために読んでください。

読む：インドのPython開発者給与

状態を維持する

Pythonの各再帰呼び出しには、独自の実行コンテキストがあります。 Pythonで再帰関数を処理するときは、各再帰呼び出しで状態をスレッド化する必要があります。 これにより、現在の状態が現在の呼び出しの実行コンテキストの一部になります。 状態をグローバルスコープで保持することもできます。

たとえば、再帰を使用して1 + 2 + 3 +4+……。+10を計算している場合。 ここで、加算する現在の数とその時点までに累積された合計が、維持する必要のある状態を形成します。 状態を維持するには、更新された現在の状態を引数として各呼び出しに渡す必要があります。 これがあなたがそれをする方法です。

def sum_numbers（current_number、accumulated_sum）

＃規範事例

＃最終状態を返す

現在の番号==11の場合：

Accumulated_sumを返します

＃再帰的なケース

＃再帰呼び出しを介して状態をスレッド化する

そうしないと：

sum_numbers（current_number + 1、accumulated_sum + current_number）を返します

または、グローバルな可変状態を使用することもできます。 このメソッドを使用して状態を維持するには、状態をグローバルスコープに保持します。

current_number = 1

Accumulated_sum = 0

def sum_numbers（）：

グローバルcurrent_number

グローバルaccumulated_sum

＃規範事例

current_number==11の場合

Accumulated_sumを返します

＃再帰的なケース

そうしないと：

Accumulated_sum = Accumulated_sum + current_number

current_number = current_number + 1

sum_numbers（）を返す

再帰的なデータ構造

データ構造は、それ自体のより小さく単純なバージョンで定義できる場合、再帰的であると見なされます。 再帰的なデータ構造の例には、リスト、ツリー、階層構造、辞書などが含まれます。リストには、要素として他のリストを含めることができます。 ツリーには、サブツリー、リーフノードなどがあります。

ここで重要なのは、再帰関数の構造は、入力として受け取るデータ構造に基づいてモデル化されることが多いということです。 したがって、再帰的なデータ構造と再帰的な関数は密接に関連しています。

フィボナッチ計算の再帰

イタリアの数学者フィボナッチは、ウサギの人口増加をモデル化するために、13世紀に最初にフィボナッチ数を定義しました。 彼は、最初の年に1組のウサギから始めて、特定の年に生まれたウサギのペアの数は、過去2年間のそれぞれに生まれたウサギのペアの数に等しいと推定しました。 これは次のように書くことができます：Fn = Fn-1 + Fn-2（基本ケース：F0=1およびF1=1）。

フィボナッチ数を計算する再帰関数を作成すると、単純な再帰が発生する可能性があります。 これは、再帰関数の定義が素朴に守られ、不必要に値を再計算することになった場合に発生します。 再計算を回避するために、lru_cacheデコレータを関数に適用できます。 結果をキャッシュし、プロセスが非効率になるのを防ぎます。

続きを読む：すべてのPython開発者が知っておくべきトップ10のPythonツール

再帰の長所と短所

再帰は、複雑なタスクをサブ問題に分割することにより、タスクを単純化するのに役立ちます。 再帰関数を使用すると、コードがよりクリーンになり、シーケンスの生成も複雑になりません。 しかし、再帰には制限があります。 呼び出しは、多くの時間とメモリを消費するため、費用がかかり非効率であることが判明する場合があります。 再帰関数もデバッグが難しい場合があります。

まとめ

この記事では、 Python再帰の概念を取り上げ、いくつかの例を使用してそれを示し、その長所と短所のいくつかについても説明しました。 これらすべての情報があれば、次のPythonインタビューで再帰関数を簡単に説明できます。

データサイエンスについて知りたい場合は、IIIT-BとupGradのデータサイエンスのPGディプロマをチェックしてください。これは、働く専門家向けに作成され、10以上のケーススタディとプロジェクト、実践的なハンズオンワークショップ、業界の専門家とのメンターシップ、1- on-1業界のメンター、400時間以上の学習、トップ企業との仕事の支援。