2010-12-17 29 views
1

給定以下遞歸函數,將由神祕(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 

這是正確的嗎?

+6

有人使用功能名稱'mysterious'在其所有的考題? :) – sje397 2010-12-17 04:58:47

+1

對不起,你自己做的時間 – KevinDTimm 2010-12-17 05:01:36

+0

有什麼神祕的嗎?編譯和運行比在SO上發佈更困難嗎? – ruslik 2010-12-17 05:08:32

回答

5

你爲什麼不直接用你選擇的語言編輯一個編輯器,編譯它並運行?我選擇了Java,但,這只是因爲我之間CygWin的我此刻的箱裝我 - 我寧願被用C :-)

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); 
    } 
} 

它輸出的數字:

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

基本上,發生的事情是,在每個級別上,你打印出數字,然後用下一個最低數字兩次調用下一個級別(除非達到零)。

旁白:從技術上說,你調用下一層與零,但是,因爲它直接返回了,它沒有對輸出的影響。

下圖有望說明這更好的,用不同的符號代表不同的層次:

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

這很有道理。所以基本上,這是雙重神祕的(x-1),導致下一個最低數字被調用兩次? – kachilous 2010-12-17 05:20:33

+0

是的,它在一個! – paxdiablo 2010-12-17 05:26:34

1

號將不打印0原因時x==0它將返回

而且,由於你有

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

將打印(固定)

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

mysterious(x-1);不會更改x的值。它只是再次調用mysterious(),這次與價值x-1

+0

什麼是「返回」意思?沒有隨後的聲明,我不習慣看到回報。 – kachilous 2010-12-17 04:58:06

+0

當處於無效函數(一個函數不返回值)時使用return函數退出函數並返回被調用函數 – Muggen 2010-12-17 04:59:03

+2

4 3 2 1 1 2 1 1 3 2 1 1 2 1 1 - 4只有一次,然後分支對於每個連續呼叫 – 2010-12-17 05:00:12

2

不,這將是

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 

因爲0將導致函數返回較早並因爲雙呼叫。

7

因爲每個函數調用都會依次產生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 
+0

這就是我曾經的想法。它實際上不是將所有這些打印在一行上,每個數字之間只有一個空格?打印語句中沒有新行'\ n'字符......這就是我認爲會發生的事情 - 但我並沒有使用C語言。 – jeremysawesome 2010-12-17 05:07:06

+0

@jeremyawesome,非常敏銳:)。我改變了輸出。 – riwalk 2010-12-17 05:15:15