Python：再帰関数の基本ケース

Question

現在、私は少しPythonの再帰関数を使って実験しています。私はそれらについてインターネット上でいくつかのことを読んできました。そして私は自分自身で簡単な関数再帰関数を作りました。しかし、私はまだベースケースの使い方がわかりません。

私はうまく設計された再帰関数は次の規則を満たしていることを知っている：

• ベースケースがあります。
• 再帰的な手順は、ベースケースに向かって動作します。
• サブ問題の解は、元の問題の解を提供します。

今私は私が持っている質問にしたがっています：複数のステートメントからベースケースを構成することは許されていますか？

つまり、以下の自己記述スクリプトの基本ケースは有効ですか？

def checkstring(n, string): 

if len(string) == 1: 
    if string == n: 
     return 1 
    else: 
     return 0 


if string[-1:] == n: 
    return 1 + checkstring(n, string[0:len(string) - 1]) 
else: 
    return checkstring(n, string[0:len(string) - 1]) 
print(checkstring('l', 'hello')) 

Answer 1

これは絶対に有効で有効な機能です。再帰関数を呼び出すことができるシナリオでは、再帰フローによって到達可能な基本ケースが存在するはずです。例えば

、以下の（愚か）再帰関数を見てみましょう：それは奇数のために呼び出された場合

def f(n): 
    if n == 0: 
     return True 
    return f(n - 2) 

この機能は5のように、そのベースケース（nは== 0）に到達することはありませんあなたはそのようなシナリオを避け、関数が得ることができるすべての可能な基本ケース（上記の例では0と1）を考える必要があります。だから、あなたは何かをするだろう

今、それは正しい機能です（数字が偶数であるかどうかをチェックするいくつかのifsがあります）。

また、機能がかなり遅くなることにも注意してください。その理由は、Pythonの文字列スライスが遅く、O（n）ではnがスライス文字列の長さであるためです。したがって、毎回文字列を再スライスすることができないように、非再帰的なソリューションを試すことをお勧めします。

また、関数が厳密に基底を持っていない場合があることに注意してください。ここで

def brute_force(a, current_digit): 
    if current_digit == 4: 
     # This means that we already chosen all 4 digits and 
     # we can just print the result 
     print a 
    else: 
     # Try to put each digit on the current_digit place and launch 
     # recursively 
     for i in range(10): 
      a[current_digit] = i 
      brute_force(a, current_digit + 1) 

a = [0] * 4 
brute_force(a, 0) 

、関数は何も返さなく、単に異なるオプションを考慮していないため、我々はベースケースを持っていない：例えば、4桁のすべての既存の組み合わせを印刷しますブルートフォース機能を、次のことを検討してください。

Answer 2

もちろん、基本ケースの唯一の要件は、関数を再帰的に呼び出さないということです。それとは別に、それはそれが望む何でもすることができます。

Answer 3

簡単に言えば、関数を再帰的に呼び出してベースケースに到達する必要がない限り、可能です。それ以外は許されます。