整蠱遞歸（尾）函數的例子

Question

我從來不喜歡與定義的發揮，尤其是在面試。 據我所知：

編輯：

尾遞歸函數是它的遞歸調用後沒有做任何更多的計算功能。

我認爲第二個不是尾遞歸，因爲它根本沒有進行遞歸調用，所以不是尾遞歸。

但是第一個是，即使它使2遞歸調用尾遞歸，它不會做以後的東西，所以我想我在這裏正確使用我的尾巴recursivness的定義。

let rec func x = 
    if x > 10 then x else func (func (x+1)) 

let f a b = a + b 

Answer 1

你的遞歸函數的定義是一個尾遞歸函數。遞歸函數簡單地定義爲一個函數，它在執行過程中的某個時刻調用自己。該定義還允許間接遞歸的函數，即它們調用另一個函數，該函數再次調用原始函數（該鏈可以是任意長度的）。

你是正確的思想，你的函數第二個是不是遞歸的。但是，第一個函數是而不是尾遞歸。

假如我們把這個函數來斯卡拉我們得到的;

@tailrec 
def func(x: Int): Int = 
{ 
    if (x > 10) x 
    else func(func(x+1)) 
} 

的@tailrec註解告訴我們，如果事情是尾遞歸。但是，編譯器會通知我們遞歸調用不在尾部位置。即兩個呼叫的內部。尾遞歸函數要求全部調用函數處於尾部位置，而不僅僅是最後的調用位於尾部位置