前言
眾所周知，遞歸函數(shù)容易爆棧，究其原因，便是函數(shù)調(diào)用前需要先將參數(shù)、運(yùn)行狀態(tài)壓棧，而遞歸則會(huì)導(dǎo)致函數(shù)的多次無返回調(diào)用，參數(shù)、狀態(tài)積壓在棧上，最終耗盡棧空間。
一個(gè)解決的辦法是從算法上解決，把遞歸算法改良成只依賴于少數(shù)狀態(tài)的迭代算法，然而此事知易行難，線性遞歸還容易，樹狀遞歸就難以轉(zhuǎn)化了，而且并不是所有遞歸算法都有非遞歸實(shí)現(xiàn)。
在這里，我介紹一種方法，利用CPS變換，把任意遞歸函數(shù)改寫成尾調(diào)用形式，以continuation鏈的形式，將遞歸占用的?？臻g轉(zhuǎn)移到堆上，避免爆棧的悲劇。
需要注意的是，這種方法并不能降低算法的時(shí)間復(fù)雜度，若是指望此法縮短運(yùn)行時(shí)間無異于白日做夢(mèng)
下文先引入尾調(diào)用、尾遞歸、
網(wǎng)友評(píng)論
