遞歸的定義是什麼

那麼，我們都知道遞歸函數吧？但究竟是什麼使得函數遞歸？我在另一個問題（Lightening effect with javascript）的評論部分進行了一個小討論，這種討論質疑了我對遞歸函數的看法，但是這也給我留下了一個相當不令人滿意的缺乏正確定義的問題。遞歸的定義是什麼

我的遞歸函數個人的定義到目前爲止是如下：

函數是遞歸的，如果它直接或間接地調用自身

注：我將提供JavaScript代碼下面的例子，但我相信他們是非常普遍的。

對於這樣一個遞歸函數的簡單示例可以是這樣的：

function a() { 
    a(); 
}

而且此：

function a() { 
    b(); 
} 

function b() { 
    a(); 
}

甚至這樣的：

function a() { 
    setTimeout(a, 1000); 
}

那些功能單位計算的無除了我之外，任何事情都會因爲他們自己調用而仍然認爲它們是遞歸的。

出現的一件事是，第三個例子不是遞歸的，因爲它使用setTimeout並且因此棧被解開。它也不是遞歸的，因爲從第次調用返回後，它不會控制第次調用。

有人提出了另一個觀點，那就是這些函數都沒有遞歸，因爲它們都不以遞歸方式計算實際問題。意味着一個問題必須通過將其分爲更小和更小的實例來解決。這裏引用維基百科文章：當一個函數是簡單的，往往較小版本的本身來定義計算機編程

遞歸的例子。然後通過組合從較簡單版本的問題中獲得的解決方案來設計該問題的解決方案。

所以這是遞歸的：

function fac(n) { 
    if (n <= 0) { 
     return 1; 
    } 
    return n * fac(n - 1); 
}

但是這不會是：

function fac(n) { 
    if (n <= 0) { 
     return 1; 
    } 
    console.log(n); 
    fac(n - 1); 
}

那麼，什麼是遞歸函數的恰當定義？究竟有沒有，還是真的只是一個哲學問題？函數必須具備哪些功能才能分類遞歸？

來源

2013-07-17 basilikum

遞歸只是簡單地定義一個問題，就簡單的情況而言（簡單的意思是「更接近」終止條件，不一定是實際上是更簡單），直到最簡單的情況是已知的情況（前面提到的終止條件）。因此，舉例來說，常年階乘函數有一個終止條件：

f(1) = 1

，並在一個簡單的方面問題的定義之一：

f(n) = n * f(n - 1), for n > 1

，我曾經聽說過的最好的解釋是這樣的：

如果你是唐納德克努斯，你明白它是什麼。
否則，找一個更接近唐納德的人問他們。

我不會叫setTimeout一個遞歸因爲a是不居然自稱。相反，它要求「系統」在稍後的日期調用它。

在那裏有終止條件也很重要。如果沒有，它仍然是遞歸的，但它無限遞歸，無異於像無限循環：

for (i = 0; i < 10; j++) {}

，並因此不可能得到什麼好處比測試其他任何時候你的堆棧溢出會發生什麼:-)

來源

2013-07-17 08:58:34 paxdiablo

Good ol'Knuth。我還沒有聽說過這個。 – 2013-07-17 09:01:17

所以一個調用自身的函數，只是爲了增加一個計數器來遍歷一個平面數組，不會是遞歸的嗎？ – basilikum

@basilikum，是的它會 - 它在數組末尾具有終止點，它具有根據「更簡單」函數定義的函數。由於棧是一個相當有限的資源，但它仍然是遞歸，就像'def sum（a，b）= sum（a + 1，b-1），如果b> 0，否則a'（對於無符號數當然）。不是一個聰明的方法來添加兩個數字，除非你只能增加或減少1，但它仍然是遞歸的。 – paxdiablo

遞歸定義？再次閱讀此行，直到你得到它。

（具有中止標準以防止無限循環的自調函數）。

來源

2013-07-17 08:54:56

所以如果它沒有中止標準它不是遞歸？ – basilikum

「遞歸的定義？再次閱讀此行，直到您找到它。」 - upvoting，直到我的鼠標按鈕中斷！：D – 2013-07-17 08:58:30

@basilikum它是，但它沒有用，因爲它永遠不會終止。 – 2013-07-17 08:59:16

遞歸是給予調用自身的函數的名稱。現在函數是否無限調用自己，它仍然是一個遞歸。

問題不一定分爲子問題。然而，在計算機科學;遞歸術語指的是用於解決問題的技術，將問題分解爲子問題，通常問題是有限的。

還有一點，遞歸是使用Stack實現的。每個函數調用堆疊在堆棧中的另一個之上，直到最後一次調用滿足基本條件，然後堆棧中的函數從上到下執行。

但是，如果沒有基礎條件或基本條件永遠不會得到滿足。那麼對該函數的無限調用將被推送到堆棧，導致內存被填滿，並且將拋出stackOverFlow異常，並且OS通過終止程序來處理它。

關於setTimeout()這是一個異步調用，並無關到遞歸，它是一個獨立的呼叫作爲來電功能不依賴於所謂的一個無論是被稱爲或其他相同的功能。

來源

2013-07-17 09:15:44 MasterMind

維基百科，你已經張貼：

遞歸在計算機程序設計時的功能較簡單，通常較小版本的本身來定義的舉例說明。然後通過結合從較簡單版本的問題獲得的解決方案來設計問題的解決方案。

所以。有一個問題，並有一個解決方案。有一個函數可以自己最小化主要問題。這個函數是遞歸的。

案例：

function a() { 
    a(); 
}

沒有問題，沒有什麼減少，有沒有辦法解決。這對我來說不是遞歸的。這只是一個無限循環。

所以另一個例子：

function a(n) { 
    if(n<.5) { 
     return n+a(Math.random()); 
    }else { 
     return n; 
    } 
} 
console.log(a(.3));

這是遞歸？編號有可能是一個問題，但找不到解決方案的主要問題。很簡單，它會隨機調用自己，直到某個標誌爲真。再次，這是一個循環。 setTimeout或setInterval同樣發生（問題的解決方案將取決於系統調用）。

來源

2013-07-17 09:37:47

遞歸的定義是什麼

回答

相關問題