什么是遞歸法執(zhí)行過程時怎樣的
什么是遞歸法執(zhí)行過程時怎樣的
遞歸法是設(shè)計和描述算法的一種有力的工具,由于它在復(fù)雜算法的描述中被經(jīng)常采用,為此在進一步介紹其他算法設(shè)計方法之前先討論它。那么你對遞歸法了解多少呢?以下是由學(xué)習(xí)啦小編整理關(guān)于什么是遞歸法的內(nèi)容,希望大家喜歡!
什么是遞歸法
能采用遞歸描述的算法通常有這樣的特征:為求解規(guī)模為N的問題,設(shè)法將它分解成規(guī)模較小的問題,然后從這些小問題的解方便地構(gòu)造出大問題的解,并且這些規(guī)模較小的問題也能采用同樣的分解和綜合方法,分解成規(guī)模更小的問題,并從這些更小問題的解構(gòu)造出規(guī)模較大問題的解。特別地,當(dāng)規(guī)模N=1時,能直接得解。
遞歸法執(zhí)行過程
遞歸算法的執(zhí)行過程分遞推和回歸兩個階段。在遞推階段,把較復(fù)雜的問題(規(guī)模為n)的求解推到比原問題簡單一些的問題(規(guī)模小于n)的求解。例如上例中,求解fib(n),把它推到求解fib(n-1)和fib(n-2)。也就是說,為計算fib(n),必須先計算fib(n-1)和fib(n-2),而計算fib(n-1)和fib(n-2),又必須先計算fib(n-3)和fib(n-4)。依次類推,直至計算fib(1)和fib(0),分別能立即得到結(jié)果1和0。在遞推階段,必須要有終止遞歸的情況。例如在函數(shù)fib中,當(dāng)n為1和0的情況。
在回歸階段,當(dāng)獲得最簡單情況的解后,逐級返回,依次得到稍復(fù)雜問題的解,例如得到fib(1)和fib(0)后,返回得到fib(2)的結(jié)果,……,在得到了fib(n-1)和fib(n-2)的結(jié)果后,返回得到fib(n)的結(jié)果。
在編寫遞歸函數(shù)時要注意,函數(shù)中的局部變量和參數(shù)只是局限于當(dāng)前調(diào)用層,當(dāng)遞推進入“簡單問題”層時,原來層次上的參數(shù)和局部變量便被隱蔽起來。在一系列“簡單問題”層,它們各有自己的參數(shù)和局部變量。
遞歸法的作用
由于遞歸引起一系列的函數(shù)調(diào)用,并且可能會有一系列的重復(fù)計算,遞歸算法的執(zhí)行效率相對較低。當(dāng)某個遞歸算法能較方便地轉(zhuǎn)換成遞推算法時,通常按遞推算法編寫程序。例如上例計算斐波那契數(shù)列的第n項的函數(shù)fib(n)應(yīng)采用遞推算法,即從斐波那契數(shù)列的前兩項出發(fā),逐次由前兩項計算出下一項,直至計算出要求的第n項。
看過“遞歸法執(zhí)行過程“的人還看了: