Java palidromeの出力を理解するのに問題があります

Question

私は、数をとり、その数に基づいて関数を実行する単純なJavaプログラムを持っています。

public class Palidrome { 
public static void main (String[] args) { 
    int N = 3; 
    System.out.println(palidrome(N)); 
} 

public static String palidrome(int i) { 
    if (i == 0) return "S"; 
    if (i == 1) return "T"; 
    return palidrome(i-2) 
      + palidrome(i-1) 
      + palidrome(i-2); 
    } 
} 

この例では、N = 3であり、出力は "TSTST"です。 Nを5に変更すると、出力は "TSTSTSTSTSTSTSTSTSTST"などとなります。

これがなぜこのような場合になるかは分かりません。 N = 5の場合、パリンドローム（i-1）とパリンドローム（i-2）は決して到達しない（i == 0）か（i == 1）

ありがとうございます！

Answer 1

これは、再帰ツリーを描画することによって理解できます。

          palindrome(5) 
             /  |   \ 
          palindrome(3)  palindrome(4) palindrome(3) 
         / |  \ ............................ 
         / |   \ 
       palindrome(1) palindrome(2) palindrome(1) 
          / |  \ 
          / |  \ 
       palindrome(0) palindrome(1) palindrome(0) 

ので回文（5）最終的に回文に到達します（0）と回文は（1）を呼び出します。
注：回帰は回文（0）と回文（1）呼び出しで終了します。

Answer 2

のは、（5） と呼ばれているN = 5

1. 回文のためにライン毎に何が起こるかを介して実行してみましょう - >私は0または1 ではありません - >回文の結果を返します（3 ）+ palindrome（4）+ palindrome（3）
2. palindrome（5）の結果を構築するには、palindrome（3）の結果が必要です。だからパリンドローム（3）が呼び出されます。 - > iは0または1ではない - >回文（1）+回文（2）+回文（1）の結果を返す
3. 回文の結果を構築するには、回文（3）。そこで回文（1）が呼び出されます。 - > i = 1なので、 "T"が返される
4. 回文（3）の結果を構築するには、回文（2）の結果が必要です。だからパリンドローム（2）が呼び出されます。 - > iは0または1ではない - >回文（0）+回文（1）+回文（0）の結果を返す
5. ここで再帰を釉薬しますが、パリンドローム（2）の結果を得る。
6. これは、パリンドローム（3）に対してパリンドローム（1）+パリンドローム（2）+パリンドローム（1）= "TSTST"を取得することを意味します。
7. この結果は、元のpalindrome（5）呼び出しに戻されます。

あなたの再帰を説明するのに役立ちます。

Answer 3

palidromeのための連続する各再帰呼び出しが近いここにあるベースの場合にあなたを持参する必要がありますので、theoritcally言っ

if (i == 0) return "S"; 
if (i == 1) return "T"; 

を

palidrome（I-1）およびpalidrome（I- 2）は決して到達しない（i == 0）または（i == 1）

これらのステートメントは最終的には到達されるが間違っているiが条件を満たすように変更されます。

どうすればvar iが変わってしまうのでしょうか？この声明を通じて：

は

return palidrome(i-2) 
      + palidrome(i-1) 
      + palidrome(i-2); 

ここでは、再帰的にpalidromeを呼び出しているが、（iが減少する）、これは最終的にベースケースにあなたを導くでしょう。

あなたの関数がbase-caseに決して当たっていなければ、無限の再帰がありますが、ここではそうではありません。物事を単純化するために

---

は、この例を見てみましょう：

は、あなたが彼を訪問ならば、あなたは一度彼を訪問場合はあなたに1個のリンゴを与える寛大な隣人、また別のものを持っていることを前提とし numberOfApplesThatYouGet= numberOfApplesThatYou'veGotIn(currentVisitNumber-1(Which is Last Visit))+numberOfApplesThatYou'veGotIn(currentVisitNumber-2)

と目を仮定することができます：彼はここで、最後の2回（つまり、実際にfibonacciシーケンスです）ので、一般的なケースであることをあなたに与えたとして、二度、彼はドロドロとしてあなたを与えることから始めましょう currentVisitNumber = n and numberOfApplesThatYouGet = a method called fib

でそう一般的なルールは次のようになります - >

fib(n)=fib(n-1)+fib(n-2) 

しかし、我々はまだ無限再帰とここベースケースを終了するbase-caseを必要とすることで、あなたの最初の訪問の条件であります

if(n==0) return 0;//if you didn't visit him you'll get nothing 
if(n==1) return 1;//if you did you'll get an apple 

ので、メソッドは次のようになります。

public int fib(int n) { 
    if(n == 0) 
     return 0; 
    else if(n == 1) 
     return 1; 
    else 
     return fib(n - 1) + fib(n - 2); 
} 

あなたは彼に3回訪問したと仮定できますが、いくつのりんごを手に入れますか？

fib(3)->fib(2)+fib(1) 

fib(2)->fib(1)+fib(0)->1+0->1 

fib(1)->1 

1+1=2 
#done 

---

またrecursionのより良い理解を形成するために、このを見てみましょう。