この記事は、の一部として公開されました データサイエンスブログソン
導入：
読者の皆様、お元気でお過ごしのことと思います。 この記事では、初心者が Python で再帰を始めるために必要な基本をすべて説明します。
再帰とは何ですか？
多くのプログラムでは、 function 他の関数を呼び出します。 例えば ：
デフォルト A(): b()
ここでは、関数「A」が関数「B」を呼び出していることがわかります。
したがって、再帰の基本的な例は、関数が他の関数の代わりにそれ自体を呼び出す場合です。
関数がそれ自体を呼び出す場合、その関数は再帰関数であると言われます。
これらには、間接再帰と直接再帰の XNUMX つのタイプがあります。
関数がその本体内からそれ自体を直接呼び出す場合、それは次のようになります。 直接再帰。 例 ：
デフォルトのrec():rec()
一方、関数が他の関数を呼び出し、その関数が呼び出し元の関数を再度呼び出すと、 が呼び出されます。 間接再帰。 例 ：
デフォルト A(): B() デフォルト B(): A()
Python での再帰の基本ケース
次のコードを考えてみましょう。
def fun1(): print("Hello 関数 2") fun2() def fun2(): print("Hello 関数 1") fun1()
何が出力されるかを予測できますか?
はい、ご想像のとおり、コードは次のようになります。 無限に印刷する !!
これは、関数が際限なく相互に呼び出し続けるためです。
しかし、これはプロセス中にメモリ全体が使い果たされることを意味するのでしょうか? いいえ、Python はそれを防ぐためにエラーを返し、そこで停止します。
エラーは次のようになります。
RuntimeError: 再帰の最大深さ1 超えました...
したがって、再帰を使用する場合は、プロセスをいつ停止するかをコンパイラに指示する賢明なコードを作成する必要があるのは明らかです。ここでベース ケースが登場します。
A 規範事例 これは、再帰呼び出しを行わずに、結果が既知または事前に決定されているケースです。 例を見ると、基本的なケースをよりよく理解できるようになります。
Python で再帰を使用して「n」個の数値の合計を計算する例
以下に、再帰を使用して最初の「n」個の数値の合計 e を計算するコードを示します。
def rec(n): if n==1 : return 1 # これは基本ケースです else: return (n+rec(n-1)) last = int(input("上限値を入力してください")) s = rec (last) print("1 から ", last," までの系列の合計は :", s)
上記のコードの出力は次のようになりました。
上限値4を入力してください。 1から4までの級数の和は：10です。
コードがどのように機能するかを理解しましょう。
「main」ブロックでは、ユーザーが入力した値 (この場合は 4) を使用して、rec 関数が呼び出されます。つまり、rec(4) が最初に呼び出されます。
ここで、コントロールは 1 行目に移り、そこで rec() のコードが始まります。 変数「n」には値 4 が割り当てられます。
n==1 は false であることが判明したため、else 部分に進みます。
5行目は戻り値をn+rec(n-1)として計算しており、n=4なので4+rec(3)となります。
したがって、値 3 で再び rec が呼び出されます。したがって、n の値が 1 に減り、基本ケースに達して 1 が返されるまで、これが繰り返されます。 返される値 10 を取得する変数 s はありません。これにより、次の行に系列の合計が出力されます。
再帰的な定義
再帰的定義は、それ自体の小さいバージョンに関して作成される定義です。 次の例を考えてみましょう。
xn = x*x*x*x…n 回
これは、再帰的定義の観点から次のように表すことができます。
xn = x*(xn-1) n > 1 の場合 (これは再帰的定義です)
=x (n=1 の場合) または 1 (n=0 の場合)
再帰関数を書く
再帰関数を書き始める前に、すべての再帰関数には少なくとも XNUMX つのケースが必要であることを理解しておく必要があります。 彼らです ：
1) 基本ケース、 解決方法がわかっているため、再帰が終了します。 言い換えれば、それは値が事前に知られている場合です。
2) 再帰的なケース これは、同じ関数への再帰呼び出しを使用して、解決しようとしている問題のより一般的なケースです。
たとえば、Power (x,n) = x * Power(x, n-1)
ここで、基本的なケースは次のようになります。
n=1 の場合は Power (x,n) = 0、または x (n=1 の場合)
注： 再帰関数の基本ケース、 到達可能である必要があります!
GCD を再帰的に計算する
再帰の概念を使用して、XNUMX つの数値の gcd を効率的に計算できます。 これは正の p と q にも当てはまります。
p>q の場合、
p と q の gcd は、p と p%q の gcd と同じです。 これが gcd を計算するための Python コードです。
デフォルト gcd(p,q):
q== 0の場合:
pを返す
gcd (q,p%q) を返す
ここでは、 基本ケースは、q が 0 で、gcd (p,0) = p の場合です。。 リダクション ステップが基本ケースに収束していることを確認するには、p%q 以降、再帰呼び出しごとに XNUMX 番目の入力が厳密に減少していることを観察します。
XNUMX つの数値の GCD を計算するこの再帰的アプローチは、 ユークリッドのアルゴリズム.
再帰と反復
この XNUMX つの単純かつ明確な違いは次のとおりです。
反復では、同じメモリ空間を使用して、コードのブロックが繰り返し実行されます。 つまり、メモリ空間は、一度割り当てられると、ループの各パスで使用されます。
一方、再帰では各ステップで関数呼び出しが行われるため、再帰呼び出しごとに新しいメモリが割り当てられます。 このため、関数呼び出しのオーバーヘッドにより、再帰関数は反復関数よりも実行速度が遅くなります。
再帰の欠点
再帰には、それ自体にいくつかの欠点もあります。 いくつかは次のとおりです:
- 反復に比べて遅いです。
- 論理的ですが、エラーが存在する場合、それを見つけるのは困難です。
- 再帰呼び出しごとに変数に個別のメモリが割り当てられるため、追加の記憶領域が必要です。
- 再帰関数は、処理または操作が大きすぎる場合にスタック オーバーフロー例外をスローすることがよくあります。
エンディングノート
それであなたの旅は終わります 再帰、関数がそれ自体を呼び出すプログラミング手法。 ご覧のとおり、再帰は当然のことながらすべてのタスクに適しているわけではなく、常に反復の代替となるわけではありません。 ただし、プログラミングの問題によってはそれが必要になる場合があります。 そのような状況では、自由に使える素晴らしいテクニックです。
著者について ：
こんにちは、私はピナック ダッタです。現在、ブバネシュワールのカリンガ工業技術大学でコンピューター サイエンス エンジニアリングを専攻している XNUMX 年生です。 私の興味は、Web 開発、競技コーディング、そして少しの機械学習です。 私のソーシャルを通じてお気軽に私とつながってください。 私はいつも同じような考えを持つ人々とチャットするのが大好きです。
Python での再帰に関するこの記事に示されているメディアは、Analytics Vidhya が所有するものではなく、著者の裁量で使用されます。
PlatoAi。 Web3の再考。 増幅されたデータインテリジェンス。
アクセスするには、ここをクリックしてください。
出典: https://www.analyticsvidhya.com/blog/2021/09/beginners-guide-to-recursion-in-python/
