Python再帰問い合わせ

Question

この関数を再帰的な形でPythonで書き直す方法を理解しているかどうか確認したいと思います。

# Recurrence Relation 
# F(n) = 7 * F(n-1) + 2 * F(n-2) 
# F(1) = 1; F(2) = 1 
# print (rr(4)) 

と私の再帰的なコードは次のとおりです： 機能がある

def rr(n): 
    return (2 * rr(n-1) + 2 * rr(n-2)) 

は、この正しいですか？また、rr（4）を "印刷"する方法は、プログラムを実行するときだけ評価できると思ったからです。

Answer 1

F（1）とF（2）の開始値である停止条件を定義していないので、コードは純粋なスタックオーバーフローを起こします。これらのケースを処理するために、nの値に応じて関数内のテストを追加します。

Answer 2

基本ケースがありません。

# F(1) = 1; F(2) = 1 

は考えてみましょう：

def rr(n): 
    if n == 1: 
     return 1 
    elif n == 2: 
     return 1 
    else: 
     return 7 * rr(n-1) + 2 * rr(n-2) 

はまた、あなたの再帰的なケースは、漸化式と一致しませんでした。それは7が現れた2を持っていました。

>>> def rr(n): 
...  if n == 1: 
...   return 1 
...  elif n == 2: 
...   return 1 
...  else: 
...   return 7 * rr(n-1) + 2 * rr(n-2) 
... 
>>> print rr(4) 
65 

Answer 3

再帰の基礎となる基本ケースは追加しませんでした。

def rr(n): 
    if n < 1: 
     raise "Invalid input" 
    if n <= 2: 
     return 1 
    return 7 * rr(n-1) + 2 * rr(n-2) 

これは、次のように実行されます：

rr(4) = 7 * rr(4-1) + 2 * rr(4-2) 
     = 7 * rr(3) + 2 * rr(2) 
     = 7 * (7 * rr(3-1) + 2 * rr(3-2)) + 2 * 1 
     = 7 * (7 * r(2) + 2 * r(1)) + 2 
     = 7 * (7 * 1 + 2 * 1) + 2 
     = 7 * 9 + 2 
     = 65 

あなたが見ることができるようにrr(2)とrr(1)が解決したことがないので、基本ケースをせずに、あなたの関数が無限に実行されます。代わりに、彼らは同じ再帰的なパスrr(1).. rr(0).. rr(-1)..etcを呼び出し続けます。