再帰関数

Question

次の再帰関数が与えられると、何が神秘的な（4）によって印刷されますか？ここで

void mysterious(int x) { 
    if (x == 0) return; 
    printf(“%d ”, x); 
    mysterious(x-1); 
    mysterious(x-1); 
} 

は私のコールスタックです：

mysterious(4) => print 4 
mysterious(3) => print 3 
mysterious(2) => print 2 
mysterious(1) => print 1 
mysterious(0) => print 0 

は、この正しいですか？あなたはそれを印刷します

mysterious(x-1); 
mysterious(x-1); 

を持っているので、それは、また

を返しますx==0それは0原因が印刷されません

Answer 1

あなたが選んだ言語でエディタに入力してコンパイルして実行してみませんか？私は、Javaを選んだが、それは、私はCygwinは現時点では私のボックスにインストールの間だという理由だけだ - 私はむしろこれは数字を出力

public class testprog { 
    public static void mysterious(int x) { 
     if (x == 0) return; 
     System.out.print(x + " "); 
     mysterious(x-1); 
     mysterious(x-1); 
    } 
    public static void main(String args[]) { 
     mysterious(4); 
    } 
} 

:-) Cを使用しているはずだ：

4 3 2 1 1 2 1 1 3 2 1 1 2 1 1 

を基本的には、各レベルで数字をプリントアウトし、次に低い数字で次のレベルを2回コールします（0になっていない限り）。

脇：技術的には、あなたがコールゼロと次の層を行わないしかし、それはすぐに返しているので、それは何も出力に影響を与えています。

次の図は、うまくいけば、異なる層を表す異なるシンボルで、これより良いを説明します：

(4) (-------------------------------) (-------------------------------) 
    {3} {-----------} {-----------} {3} {-----------} {-----------} 
      [2] [1] [1] [2] [1] [1]   [2] [1] [1] [2] [1] [1] 

Answer 2

号（固定）

4 3 2 1 1 2 1 1 3 2 1 1 2 1 1 

mysterious(x-1);xの値は変更されません。 0は、関数がそのせいで、二重のコールの以前の返却とする原因になりますので、それだけで、再び値x-1

Answer 3

ないと、この時間をmysterious()を呼び出し、それが

mysterious(4) => print 4 
mysterious(3) => print 3 
mysterious(2) => print 2 
mysterious(1) => print 1 
mysterious(1) => print 1 
mysterious(2) => print 2 
mysterious(1) => print 1 
mysterious(1) => print 1 
mysterious(3) => print 3 
mysterious(2) => print 2 
mysterious(1) => print 1 
mysterious(1) => print 1 
mysterious(2) => print 2 
mysterious(1) => print 1 
mysterious(1) => print 1 

になります。

Answer 4

すべての関数呼び出しが2つの関数呼び出しを順番に行うので、あなたは再帰を「木」として視覚化して話すことができ、ツリー上で先行走査を行います。

それはこのようなものになります：あなたが持っている実行の順序がある

      4 
          | 
       3----------+----------3 
       |      | 
      2----+----2   2----+----2 
      |   |   |   | 
     1--+--1 1--+--1  1--+--1 1--+--1 

を：

• 印刷X-1
• コールで数
• コール機能再びx-1の関数

これが行うことで、当社の「木の可視化」に対応するであろう：

• 印刷ルート
• を左ノード
• トラバース右ノード

トラバース出力は次のようになります。

4 3 2 1 1 2 1 1 3 2 1 1 2 1 1