2013-02-24 121 views
2

我是新的Haskell,仍然試圖理解一些基礎知識。在編寫遞歸函數時,我自然會以遞歸或尾遞歸的方式編寫它們,而不必有意識地選擇一個。將遞歸函數轉換爲尾遞歸

我的問題是:

  1. 鑑於任何遞歸函數,有沒有一種簡單的方法將其轉換爲尾遞歸?

  2. 給定一個尾遞歸函數,有沒有簡單的方法將其轉換爲遞歸?

示例功能

addOne [] = [] 
addOne (x:xs) = (x+1):addOne xs 

此外,寫一個函數的時候,什麼是一個簡單的方法來判斷是否尾遞歸是在替代比較合適?

+9

「給定一個尾遞歸函數,是否有簡單的方法將其轉換爲遞歸?」 - 每個尾遞歸函數都是自然遞歸的,不是嗎? – 2013-02-24 20:44:03

+0

是的,但這與我的問題無關。編寫一個遞歸和尾遞歸函數是兩個完全不同的程序(語法上),可以完成相同的任務。所以可以轉換爲其他。 – AnchovyLegend 2013-02-24 20:50:57

+0

@Mi:不,尾遞歸函數總是遞歸的,函數不是與它自身「完全不同」,既不是語法也不是任何其他方面。 – 2013-02-25 00:43:30

回答

2

我是Haskell的新手。從我讀過的內容可以看出,Haskell社區對顯式遞歸是不滿意的。相反,Haskell鼓勵程序員使用標準函數,如map,filter,foldl,foldr等,它們封裝了常見的遞歸操作。例如,

addOne [] = [] 
addOne (x:xs) = (x+1):addOne xs 

可以寫成

addOne xs = map (+1) xs 

,或者要進一步使用無點式的步驟,如

addOne = map (+1) 

有可能的情況下,這些標準功能別不容易適應,你必須編寫自己的遞歸函數。但是,我相信他們覆蓋了90%的情況下你可能會試圖實現顯式遞歸。

我知道這並不完全回答你的問題,但我希望它給你一些想法來考慮。

1

鑑於任何遞歸函數,是否有一種簡單的方法將其轉換爲 尾遞歸?

給出一個尾遞歸函數,有一個簡單的方法來將其轉換爲遞歸?

是的。什麼也不做,沒有任何東西可以完成(老謝),就像@Joachim Breitner已經告訴你的那樣。但是您對recursive的定義似乎偏離了常見的定義,因此您可能會告訴我們您的意思。

+0

+1,對於居高臨下的無用答案。 – AnchovyLegend 2013-02-25 01:26:58