什麼是遞迴法執行過程時怎樣的

　　遞迴法是設計和描述演算法的一種有力的工具，由於它在複雜演算法的描述中被經常採用，為此在進一步介紹其他演算法設計方法之前先討論它。那麼你對遞迴法瞭解多少呢?以下是由小編整理關於什麼是遞迴法的內容，希望大家喜歡!

　　什麼是遞迴法

　　能採用遞迴描述的演算法通常有這樣的特徵：為求解規模為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***的結果。

　　在編寫遞迴函式時要注意，函式中的區域性變數和引數只是侷限於當前呼叫層，當遞推進入“簡單問題”層時，原來層次上的引數和區域性變數便被隱蔽起來。在一系列“簡單問題”層，它們各有自己的引數和區域性變數。

　　遞迴法的作用

　　由於遞迴引起一系列的函式呼叫，並且可能會有一系列的重複計算，遞迴演算法的執行效率相對較低。當某個遞迴演算法能較方便地轉換成遞推演算法時，通常按遞推演算法編寫程式。例如上例計算斐波那契數列的第n項的函式fib***n***應採用遞推演算法，即從斐波那契數列的前兩項出發，逐次由前兩項計算出下一項，直至計算出要求的第n項。