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