首頁猿問每個(gè)遞歸都能轉(zhuǎn)換成迭代嗎？

每個(gè)遞歸都能轉(zhuǎn)換成迭代嗎？

算法與數(shù)據(jù)結(jié)構(gòu) 源碼

慕萊塢森 2019-06-19 17:27:20

每個(gè)遞歸都能轉(zhuǎn)換成迭代嗎？A Reddit線程提出了一個(gè)明顯有趣的問題：尾遞歸函數(shù)可以很小地轉(zhuǎn)化為迭代函數(shù)。其他的，可以通過使用顯式堆棧進(jìn)行轉(zhuǎn)換。能，會(huì)，可以每一，每個(gè)遞歸轉(zhuǎn)化為迭代？文章中的(計(jì)數(shù)器？)示例是對(duì)：(define (num-ways x y) (case ((= x 0) 1) ((= y 0) 1) (num-ways2 x y) )) (define (num-ways2 x y) (+ (num-ways (- x 1) y) (num-ways x (- y 1))

查看完整描述

3 回答

慕沐林林

TA貢獻(xiàn)2016條經(jīng)驗(yàn) 獲得超9個(gè)贊

是否總是可以為每個(gè)遞歸函數(shù)編寫非遞歸形式？

是。一個(gè)簡單的形式證明就是證明預(yù)遞歸非遞歸演算(如Goto)都是圖靈完整的。由于所有圖靈完全計(jì)算器在表達(dá)能力上都是完全等價(jià)的，所以所有遞歸函數(shù)都可以用非遞歸圖靈全演算來實(shí)現(xiàn)。

不幸的是，我無法找到GotoOnline的一個(gè)好的、正式的定義，因此這里有一個(gè)：

Goto程序是一系列命令P在寄存器機(jī)使.P如下之一：

HALT
，這將停止執(zhí)行
r = r + 1
哪里
r
是任何登記冊(cè)
r = r – 1
哪里
r
是任何登記冊(cè)
GOTO x
哪里
x
是個(gè)標(biāo)簽
IF r ≠ 0 GOTO x
哪里
r
是任何登記冊(cè)
x
是個(gè)標(biāo)簽
一個(gè)標(biāo)簽，后面跟著上面的任何命令。

然而，遞歸函數(shù)和非遞歸函數(shù)之間的轉(zhuǎn)換并不總是那么簡單(除了調(diào)用堆棧的盲目手動(dòng)重新實(shí)現(xiàn))。

有關(guān)更多信息，請(qǐng)參見這個(gè)答案.

反對(duì) 回復(fù) 2019-06-19

Helenr

TA貢獻(xiàn)1780條經(jīng)驗(yàn) 獲得超4個(gè)贊

遞歸在實(shí)際的解釋器或編譯器中被實(shí)現(xiàn)為堆?；蝾愃频慕Y(jié)構(gòu)。因此，您當(dāng)然可以將遞歸函數(shù)轉(zhuǎn)換為迭代對(duì)應(yīng)函數(shù)。因?yàn)樗偸沁@樣做的(如果是自動(dòng)的)..您將只是臨時(shí)地復(fù)制編譯器的工作，而且可能是以一種非常丑陋和低效的方式復(fù)制編譯器的工作。

反對(duì) 回復(fù) 2019-06-19