2013-05-19 78 views
1

我和我的朋友在爭論我們是否需要分析家庭作業的算法是否是尾遞歸的,但他堅持認爲它是。因此,該算法看起來是這樣的:這個程序是否是遞歸的?

SomeAlgo(x) 
{ 
    x--; 

    if (x > 1) 
    { 
     SomeAlgo(x); 
    } 
    else 
    { 
     return x; 
    } 
} 

我告訴他這是不是尾遞歸,因爲SomeAlgo(X)是不是要執行的最後一條語句。我們需要一個基礎案例,但我們不需要。如果我們有一個基本情況,基本情況下的代碼將是第一個要執行的事情,並且對自身的調用(返回要返回的值)將是最後一個。

如果它不是尾遞歸,你能告訴我需要做什麼才能使它尾遞歸嗎?

+2

什麼編程語言,這是?如果您指定您在標記中使用的編程語言,您將獲得更多視圖。 –

回答

3

SomeAlgo(X)要執行的最後一條語句,如果X大於1

+0

我以爲你需要有返回算法(x)纔能有一個尾遞歸算法。最後執行的語句是返回x而不是算法(x)。我錯了嗎? –

+3

如果算法使用尾遞歸的唯一可能方式是將另一個調用返回給它本身,那麼「尾遞歸」的每個實現都將導致無限遞歸,並因此導致stackoverflowerror,因爲它永遠無法返回靜態值。在你的算法的情況下,'return x;'其中x <= 1是你的基本情況。 – jonhopkins

+0

因此,否則返回x是基本情況,對不對?但這不是第一個要執行的語句,而是執行的最後一行代碼,對吧? –