-
遞歸法
鎖定
遞歸法是設計和描述算法的一種有力的工具,由於它在複雜算法的描述中被經常採用,為此在進一步介紹其他算法設計方法之前先討論它。
- 中文名
- 遞歸法
- 外文名
- Recursive method
遞歸法基本介紹
能採用遞歸描述的算法通常有這樣的特徵:為求解規模為N的問題,設法將它分解成規模較小的問題,然後從這些小問題的解方便地構造出大問題的解,並且這些規模較小的問題也能採用同樣的分解和綜合方法,分解成規模更小的問題,並從這些更小問題的解構造出規模較大問題的解。特別地,當規模N=1時,能直接得解。
遞歸法執行過程
遞歸算法的執行過程分遞推和迴歸兩個階段。在遞推階段,把較複雜的問題(規模為n)的求解推到比原問題簡單一些的問題(規模小於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),分別能立即得到結果1和0。在遞推階段,必須要有終止遞歸的情況。例如在函數fib中,當n為1和0的情況。
在迴歸階段,當獲得最簡單情況的解後,逐級返回,依次得到稍複雜問題的解,例如得到fib(1)和fib(0)後,返回得到fib(2)的結果,……,在得到了fib(n-1)和fib(n-2)的結果後,返回得到fib(n)的結果。