再帰という用語は、それ自体に関して何かを定義するプロセスとして定義できます。簡単に言うと、関数がそれ自体を直接的または間接的に呼び出すプロセスです。
再帰を使用する利点
- 複雑な関数は、再帰を利用して小さなサブ問題に分割できます。
- シーケンスの作成は、ネストされた反復を使用するよりも再帰を使用する方が簡単です。
- 再帰関数により、コードがシンプルかつ効果的に見えます。
再帰を使用するデメリット
- 再帰呼び出しには大量のメモリと時間が消費されるため、使用コストが高くなります。
- 再帰関数はデバッグが困難です。
- 再帰の背後にある理由をじっくり考えるのが難しい場合があります。
構文：
def func(): <-- | | (recursive call) | func() ---->
例 1: フィボナッチ数列とは、0、1、1、2、3、5、8…の整数列です。
Python3
# Program to print the fibonacci series upto n_terms> # Recursive function> def> recursive_fibonacci(n):> >if> n <>=> 1>:> >return> n> >else>:> >return>(recursive_fibonacci(n>->1>)>+> recursive_fibonacci(n>->2>))> n_terms>=> 10> # check if the number of terms is valid> if> n_terms <>=> 0>:> >print>(>'Invalid input ! Please input a positive value'>)> else>:> >print>(>'Fibonacci series:'>)> for> i>in> range>(n_terms):> >print>(recursive_fibonacci(i))> |
Inkscape vs Gimp
>
>出力
Fibonacci series: 0 1 1 2 3 5 8 13 21 34>
例 2: 6 の階乗は 6 と表されます。 = 1*2*3*4*5*6 = 720。
Python3
# Program to print factorial of a number> # recursively.> # Recursive function> def> recursive_factorial(n):> >if> n>=>=> 1>:> >return> n> >else>:> >return> n>*> recursive_factorial(n>->1>)> # user input> num>=> 6> # check if the input is valid or not> if> num <>0>:> >print>(>'Invalid input ! Please enter a positive number.'>)> elif> num>=>=> 0>:> >print>(>'Factorial of number 0 is 1'>)> else>:> >print>(>'Factorial of number'>, num,>'='>, recursive_factorial(num))> |
>
>出力
Factorial of number 6 = 720>
末尾再帰とは何ですか?
関数の最後のプロシージャが再帰呼び出しとなる、ユニークなタイプの再帰。新しいスタック フレームを生成する代わりに、現在のスタック フレームでリクエストを実行し、出力を返すことで、再帰を自動化できます。末尾再帰はコンパイラによって最適化され、末尾再帰以外の関数よりも優れたものになる場合があります。
非末尾再帰関数の代わりに末尾再帰関数を利用してプログラムを最適化することは可能ですか?
n の階乗を計算するために以下に与えられた関数を考慮すると、この関数は最初は末尾再帰関数のように見えますが、非末尾再帰関数であることがわかります。よく観察すると、Recur_facto(n-1) によって返された値が Recur_facto(n) で使用されていることがわかります。したがって、Recur_facto(n-1) への呼び出しは Recur_facto(n) によって行われる最後の処理ではありません。
Python3
Javaの列挙型の値
# Program to calculate factorial of a number> # using a Non-Tail-Recursive function.> # non-tail recursive function> def> Recur_facto(n):> > >if> (n>=>=> 0>):> >return> 1> > >return> n>*> Recur_facto(n>->1>)> > # print the result> print>(Recur_facto(>6>))> |
>
>出力
アルファベットの数字
720>
指定された関数 Recur_facto を末尾再帰関数として書くことができます。このアイデアは、もう 1 つの引数を使用し、2 番目の引数で階乗の値を受け入れることです。 n が 0 に達すると、目的の数値の階乗の最終値を返します。
Python3
# Program to calculate factorial of a number> # using a Tail-Recursive function.> # A tail recursive function> def> Recur_facto(n, a>=> 1>):> > >if> (n>=>=> 0>):> >return> a> > >return> Recur_facto(n>-> 1>, n>*> a)> > # print the result> print>(Recur_facto(>6>))> |
>
>出力
720>