概述
遞歸是設計和描述算法的一種有力的工具，由于它在複雜算法的描述中被經常采用，為此在進一步介紹其他算法設計方法之前先讨論它。
能采用遞歸描述的算法通常有這樣的特征：為求解規模為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項。
應用
求解約束矩陣方程組和相應的最小二乘問題是最近研究的一個非常活躍的領域，并且具有廣泛的應用範圍，例如：結構設計，系統識别，結構動力學和自動化控制理論。
矩陣方程組(AX，XB)=(C，D)的一般公共解、一般最小二乘解以及對稱最小二乘解。
主要問題表述如下：
問題Ⅰ：給定A，B，C，D∈Rn×n，求大型矩陣方程組(AX，XB)=(C，D)的一般公共解X∈Rn×n。
問題Ⅱ：給定A，B，C，D∈Rn×n，求大型矩陣方程組(AX，XB)=(C，D)的一般最小二乘解X∈Rn×n。
問題Ⅲ：給定A，B，C，D∈Rn×n，求大型矩陣方程組(AX，XB)=(C，D)的對稱最小二乘解X∈Rn×n。
