遞歸的受理方法和技巧

A. 什麼是遞歸函數 怎樣實現遞歸

遞歸就是一個函數在它的函數體內調用它自身。執行遞歸函數將反復調用其自身，每調用一次就進入新的一層。遞歸函數必須有結束條件。

當函數在一直遞推，直到遇到牆後返回，這個牆就是結束條件。

所以遞歸要有兩個要素，結束條件與遞推關系。

遞歸有兩個基本要素：

（1）邊界條件：確定遞歸到何時終止，也稱為遞歸出口。

（2）遞歸模式：大問題是如何分解為小問題的，也稱為遞歸體。遞歸函數只有具備了這兩個要素，才能在有限次計算後得出結果

在遞歸函數中，調用函數和被調用函數是同一個函數，需要注意的是遞歸函數的調用層次，如果把調用遞歸函數的主函數稱為第0層，進入函數後，首次遞歸調用自身稱為第1層調用；從第i層遞歸調用自身稱為第i+1層。反之，退出第i+1層調用應該返回第i層。

一個遞歸函數的調用過程類似於多個函數的嵌套的調用，只不過調用函數和被調用函數是同一個函數。為了保證遞歸函數的正確執行，系統需設立一個工作棧。具體地說，遞歸調用的內部執行過程如下：

（1）運動開始時，首先為遞歸調用建立一個工作棧，其結構包括值參、局部變數和返回地址；

（2）每次執行遞歸調用之前，把遞歸函數的值參和局部變數的當前值以及調用後的返回地址壓棧；

（3）每次遞歸調用結束後，將棧頂元

(1)遞歸的受理方法和技巧擴展閱讀：

遞歸就是某個函數直接或間接地調用了自身，這種調用方式叫做遞歸調用。說白了，還是函數調用。既然是函數調用，那麼就有一個雷打不動的原則：所有被調用的函數都將創建一個副本，各自為調用者服務，而不受其他函數的影響。

你的ff函數，遞歸多少次，就有多少個副本，再利用內存的棧式管理，反向退出。這個最好找一下「棧」這方面的東西看看，挺容易的，就像子彈匣一樣，先進後出。

從某種意義上說，這是不對的，因為就像剛才說的，一旦被調用，他將在內存中復制出一份代碼，再被調用就再復制一份，換句話說，你可以吧同一個函數的多次調用理解稱謂多個不同函數的一次調用，這樣也會會簡單些。

再說=1和=0是為什麼退出。遞歸，很需要注意的就是死遞歸，也就是說，某一個函數進入了無限調用自身的情況，永無止境地消耗內存等資源，這在編程方面是一大忌。

但凡是遞歸的函數，一定會在某一個地方存在能夠返回上一層函數的代碼，否則必定死遞歸。ff函數中，那個else就是返回的出口，你可以這樣想，如果沒有那個if來進行判斷，你遞歸到什麼時候算完？ff是不是會一直調用自己。

因為一旦某個函數A中調用了函數B（或者自己），那麼A中的代碼會停在調用的位置，而轉向B中去執行，同理，如果B又調用函數C，那麼B又停在調用的位置，去執行C，如果無限調用，那麼程序是永遠不會結束的。

當然，也有這種情況，A調用B，然後繼續自己的代碼，不管B的死活，這種不在我們的討論范圍內，因為那牽扯到另一種編程方式：多線程。

B. 遞歸方法的定義

1、定義是遞歸的：

（1）n!的遞歸實現：

遞歸方法：

public class Method { int fun(int n){ if(n==1) return 1; else
return(fun(n-1)*n);
}
}
public class RecursionDemo { public static void main (String[] args){
Method m=new Method(); int num=m.fun(3);
System.out.println(num);
}
}

遞歸方法分析：

（1）該方法是直接遞歸，即自己調用自己。

例如：在執行fun(3)的時候，先執行fun（2）*3，而fun（2）=fun（1）*2，fun（1）=1。

（2）遞歸過程將問題的規模逐步縮小，參數的大小每次減1。一個個重復的過程，通過調用自身，減少了代碼量。

（3）因為遞歸調用語句是在最後一句，因此，這種遞歸方式也稱為尾遞歸。

2、數據結構是遞歸的：

單鏈表的存儲結構定義。

3、問題的求解是遞歸的：

#include<stdio.h> #include<malloc.h> #include<stdlib.h>#define LIST_INIT_SIZE 100
#define LISTINCREMENT 10#define OVERFLOW -2#define ERROR 0
#define OK 1typedef int ElemType;

typedef struct{ //存儲結構 ElemType *elem; //指針類型 int length;
int listsize;
}SqList;//順序表的結構類型 typedef int Status;

Status InitList(SqList &L){
L.elem=(ElemType *)malloc(LIST_INIT_SIZE*sizeof(ElemType));//動態分配存儲空間 if(!L.elem) exit(OVERFLOW); //分配失敗退出 L.length=0; //空表 L.listsize=LIST_INIT_SIZE; //初始存儲容量 return OK;
}

Status ListInsert(SqList &L,int i,ElemType e){//在第 i 個元素前插入一個新的元素e if(i<1 || i > L.length+1) return ERROR; //i值不合法 if(L.length>=L.listsize) //存儲空間不足 {
ElemType * newbase=(ElemType *)realloc(L.elem,(LIST_INIT_SIZE+LISTINCREMENT)*sizeof(ElemType));
if(!newbase) exit(OVERFLOW); //分配失敗 L.elem=newbase;
L.listsize=LIST_INIT_SIZE+LISTINCREMENT;
}
for (int j=L.length; j>=i; --j)
L.elem[j]=L.elem[j-1];
L.elem[i-1]=e;
L.length++;return OK;
}

Status ListEmpty(SqList L){ //判斷順序表是否為空return L.length == 0;
}

Status ListPrint(SqList &L) {
printf(" 順序表為： ");
if (ListEmpty(L)) {
printf(" 空。 ");
return ERROR;
}
for (int i=0; i<L.length; ++i)
{
printf("%-4d ", L.elem[i]);
}
printf(" ");
return OK;
}int Sum(SqList L,int i){ if(i==L.length) return 0; else
return(L.elem[i]+Sum(L,i+1));
}

main(){

SqList L;
ElemType e;
int i,j;
InitList(L);


printf(" 請輸入你想創建的順序表中元素的個數： ");
scanf("%d",&i);
if(i<1) printf(" 您輸入的值有誤，無法創建順序表。 ");
else {
printf(" 請您依次輸入您想創建的順序表的元素： ");
for(j=1;j<=i;j++)
{
scanf("%d",&e);
ListInsert(L,L.length+1,e); //尾插 }
}
ListPrint(L); //遍歷順序表 int result=Sum(L,0);
printf( "順序表所有元素的和為：%d",result);
}

這個程序是求解順序表的元素的和，從順序表的第一個元素開始，依次向後查找元素，並進行求和運算。

C. 誰能給講一下遞歸

遞歸是一種重要的編程技術。該方法用於讓一個函數從其內部調用其自身。一個示例就是計算階乘。0 的階乘被特別地定義為 1。 更大數的階乘是通過計算 1 * 2 * ...來求得的，每次增加 1，直至達到要計算其階乘的那個數。

下面的段落是用文字定義的計算階乘的一個函數。

「如果這個數小於零，則拒絕接收。如果不是一個整數，則將其向下舍入為相鄰的整數。如果這個數為 0，則其階乘為 1。如果這個數大於 0，則將其與相鄰較小的數的階乘相乘。」

要計算任何大於 0 的數的階乘，至少需要計算一個其他數的階乘。用來實現這個功能的函數就是已經位於其中的函數；該函數在執行當前的這個數之前，必須調用它本身來計算相鄰的較小數的階乘。這就是一個遞歸示例。

遞歸和迭代（循環）是密切相關的 — 能用遞歸處理的演算法也都可以採用迭代，反之亦然。確定的演算法通常可以用幾種方法實現，您只需選擇最自然貼切的方法，或者您覺得用起來最輕松的一種即可。

顯然，這樣有可能會出現問題。可以很容易地創建一個遞歸函數，但該函數不能得到一個確定的結果，並且不能達到一個終點。這樣的遞歸將導致計算機執行一個「無限」循環。下面就是一個示例：在計算階乘的文字描述中遺漏了第一條規則（對負數的處理） ，並試圖計算任何負數的階乘。這將導致失敗，因為按順序計算 -24 的階乘時，首先不得不計算 -25 的階乘；然而這樣又不得不計算 -26 的階乘；如此繼續。很明顯，這樣永遠也不會到達一個終止點。

因此在設計遞歸函數時應特別仔細。如果懷疑其中存在著無限遞歸的可能，則可以讓該函數記錄它調用自身的次數。如果該函數調用自身的次數太多，即使您已決定了它應調用多少次，就自動退出。

下面仍然是階乘函數，這次是用 JScript 代碼編寫的。

// 計算階乘的函數。如果傳遞了
// 無效的數值（例如小於零），
// 將返回 -1，表明發生了錯誤。若數值有效，
// 把數值轉換為最相近的整數，並
// 返回階乘。
function factorial(aNumber) {
aNumber = Math.floor(aNumber); // 如果這個數不是一個整數，則向下舍入。
if (aNumber < 0) { // 如果這個數小於 0，拒絕接收。
return -1;
}
if (aNumber == 0) { // 如果為 0，則其階乘為 1。
return 1;
}
else return (aNumber * factorial(aNumber - 1)); // 否則，遞歸直至完成。
}

D. 講一下c語言中遞歸函數的使用方法

遞歸函數有三點要求：

1，遞歸的終止點，即遞歸函數的出口

2，不斷的遞歸調用自身

3，遞歸函數主體內容，即遞歸函數需要做的事情

ps：3一般可以放在2的前面或者後面，一般1放最前面。另外，2和3可以根據不同的需要合並，比如，有時候遞歸函數的主體就是返回調用下層函數所得到的結果。

具體例子如下：

voidfun(intn)
{
if(n<=0)return;//1這是遞歸的終點，即出口
fun(n-1);//2、遞歸函數自身的調用
cout<<n<<endl;//3遞歸函數的主體內容
}

2,3合並的情況

intfun(intn)
{
if(n<=0)return0;
returnfun(n-1)+fun(n-2);//23合並
}

E. 遞歸的原理解釋

遞歸的原理解釋：
遞歸，是函數實現的一個很重要的環節，很多程序中都或多或少的使用了遞歸函數。遞歸的意思就是函數自己調用自己本身，或者在自己函數調用的下級函數中調用自己。
遞歸之所以能實現，是因為函數的每個執行過程都在棧中有自己的形參和局部變數的拷貝，這些拷貝和函數的其他執行過程毫不相干。這種機制是當代大多數程序設計語言實現子程序結構的基礎，是使得遞歸成為可能。假定某個調用函數調用了一個被調用函數，再假定被調用函數又反過來調用了調用函數。這第二個調用就被稱為調用函數的遞歸，因為它發生在調用函數的當前執行過程運行完畢之前。而且，因為這個原先的調用函數、現在的被調用函數在棧中較低的位置有它獨立的一組參數和自變數，原先的參數和變數將不受影響，所以遞歸能正常工作。程序遍歷執行這些函數的過程就被稱為遞歸下降。
程序員需保證遞歸函數不會隨意改變靜態變數和全局變數的值，以避免在遞歸下降過程中的上層函數出錯。程序員還必須確保有一個終止條件來結束遞歸下降過程，並且返回到頂層。

F. 遞歸主方法

遞歸的主要方法是什麼？

一、遞歸演算法
遞歸演算法（英語：recursion algorithm）在計算機科學中是指一種通過重復將問題分解為同類的子問題而解決問題的方法。遞歸式方法可以被用於解決很多的計算機科學問題，因此它是計算機科學中十分重要的一個概念。絕大多數編程語言支持函數的自調用，在這些語言中函數可以通過調用自身來進行遞歸。計算理論可以證明遞歸的作用可以完全取代循環，因此在很多函數編程語言（如Scheme）中習慣用遞歸來實現循環。
二、遞歸程序
在支持自調的編程語言中，遞歸可以通過簡單的函數調用來完成，如計算階乘的程序在數學上可以定義為：

這一程序在Scheme語言中可以寫作：
1
(define (factorial n) (if (= n 0) 1 (* n (factorial (- n 1)))))
不動點組合子
即使一個編程語言不支持自調用，如果在這語言中函數是第一類對象（即可以在運行期創建並作為變數處理），遞歸可以通過不動點組合子（英語：Fixed-point combinator）來產生。以下Scheme程序沒有用到自調用，但是利用了一個叫做Z 運算元（英語：Z combinator）的不動點組合子，因此同樣能達到遞歸的目的。
1
(define Z (lambda (f) ((lambda (recur) (f (lambda arg (apply (recur recur) arg)))) (lambda (recur) (f (lambda arg (apply (recur recur) arg)))))))(define fact (Z (lambda (f) (lambda (n) (if (<= n 0) 1 (* n (f (- n 1))))))))
這一程序思路是，既然在這里函數不能調用其自身，我們可以用 Z 組合子應用(application)這個函數後得到的函數再應用需計算的參數。
尾部遞歸
尾部遞歸是指遞歸函數在調用自身後直接傳回其值，而不對其再加運算。尾部遞歸與循環是等價的，而且在一些語言（如Scheme中）可以被優化為循環指令。 因此，在這些語言中尾部遞歸不會佔用調用堆棧空間。以下Scheme程序同樣計算一個數字的階乘，但是使用尾部遞歸：
1
(define (factorial n) (define (iter proct counter) (if (> counter n) proct (iter (* counter proct) (+ counter 1)))) (iter 1 1))
三、能夠解決的問題
數據的定義是按遞歸定義的。如Fibonacci函數。
問題解法按遞歸演算法實現。如Hanoi問題。
數據的結構形式是按遞歸定義的。如二叉樹、廣義表等。
四、遞歸數據
數據類型可以通過遞歸來進行定義，比如一個簡單的遞歸定義為自然數的定義：「一個自然數或等於0，或等於另一個自然數加上1」。Haskell中可以定義鏈表為：
1
data ListOfStrings = EmptyList | Cons String ListOfStrings
這一定義相當於宣告「一個鏈表或是空串列，或是一個鏈表之前加上一個字元串」。可以看出所有鏈表都可以通過這一遞歸定義來達到。

G. 請教高人 遞歸演算法編寫思路技巧

一個子程序（過程或函數）的定義中又直接或間接地調用該子程序本身，稱為遞歸。遞歸是一種非常有用的程序設計方法。用遞歸演算法編寫的程序結構清晰，具有很好的可讀性。遞歸演算法的基本思想是：把規模大的、較難解決的問題變成規模較小的、易解決的同一問題。規模較小的問題又變成規模更小的問題，並且小到一定程度可以直接得出它的解，從而得到原來問題的解。
利用遞歸演算法解題，首先要對問題的以下三個方面進行分析：
一、決定問題規模的參數。需要用遞歸演算法解決的問題，其規模通常都是比較大的，在問題中決定規模大小（或問題復雜程度）的量有哪些？把它們找出來。
二、問題的邊界條件及邊界值。在什麼情況下可以直接得出問題的解？這就是問題的邊界條件及邊界值。
三、解決問題的通式。把規模大的、較難解決的問題變成規模較小、易解決的同一問題，需要通過哪些步驟或等式來實現？這是解決遞歸問題的難點。把這些步驟或等式確定下來。
把以上三個方面分析好之後，就可以在子程序中定義遞歸調用。其一般格式為：
if 邊界條件 1 成立 then
賦予邊界值 1
【 elseif 邊界條件 2 成立 then
賦予邊界值 2
┇ 】
else
調用解決問題的通式
endif
例 1 ： 計算勒讓德多項式的值

x 、 n 由鍵盤輸入。
分析： 當 n ＝ 0 或 n ＝ 1 時，多項式的值都可以直接求出來，只是當 n ＞ 1 時，才使問題變得復雜，決定問題復雜程度的參數是 n 。根據題目提供的已知條件，我們也很容易發現，問題的邊界條件及邊界值有兩個，分別是：當 n ＝ 0 時 P n (x) ＝ 1 和當 n ＝ 1 時 P n (x) ＝ x 。解決問題的通式是：
P n (x) ＝ ((2n － 1)P n － 1 (x) － (n － 1)P n － 2 (x)) ／ n 。
接下來按照上面介紹的一般格式定義遞歸子程序。
function Pnx(n as integer)
if n ＝ 0 then
Pnx ＝ 1
elseif n ＝ 1 then
Pnx ＝ x
else
Pnx ＝ ((2*n － 1)*Pnx(n － 1) － (n － 1)*Pnx(n － 2)) ／ n
endif
end function
例 2 ： Hanoi 塔問題：傳說印度教的主神梵天創造世界時，在印度北部佛教聖地貝拿勒斯聖廟里，安放了一塊黃銅板，板上插著三根寶石針，在其中一根寶石針上，自下而上地放著由大到小的 64 個金盤。這就是所謂的梵塔（ Hanoi ），如圖。梵天要求僧侶們堅持不渝地按下面的規則把 64 個盤子移到另一根針上：

(1) 一次只能移一個盤子；
(2) 盤子只許在三根針上存放；
(3) 永遠不許大盤壓小盤。
梵天宣稱，當把他創造世界之時所安放的 64 個盤子全部移到另一根針上時，世界將在一聲霹靂聲中毀滅。那時，他的虔誠的信徒都可以升天。
要求設計一個程序輸出盤子的移動過程。
分析： 為了使問題更具有普遍性，設共有 n 個金盤，並且將金盤由小到大依次編號為 1 ， 2 ，…， n 。要把放在 s(source) 針上的 n 個金盤移到目的針 o(objective) 上，當只有一個金盤，即 n ＝ 1 時，問題是比較簡單的，只要將編號為 1 的金盤從 s 針上直接移至 o 針上即可。可定義過程 move(s,1,o) 來實現。只是當 n>1 時，才使問題變得復雜。決定問題規模的參數是金盤的個數 n ；問題的邊界條件及邊界值是：當 n ＝ 1 時， move(s,1,o) 。
當金盤不止一個時，可以把最上面的 n － 1 個金盤看作一個整體。這樣 n 個金盤就分成了兩個部分：上面 n － 1 個金盤和最下面的編號為 n 的金盤。移動金盤的問題就可以分成下面三個子問題（三個步驟）：
(1) 藉助 o 針，將 n － 1 個金盤（依照上述法則）從 s 針移至 i(indirect) 針上；
(2) 將編號為 n 的金盤直接從 s 針移至 o 針上；
(3) 藉助 s 針，將 i 針上的 n － 1 個金盤（依照上述法則）移至 o 針上。如圖

其中第二步只移動一個金盤，很容易解決。第一、第三步雖然不能直接解決，但我們已經把移動 n 個金盤的問題變成了移動 n － 1 個金盤的問題，問題的規模變小了。如果再把第一、第三步分別分成類似的三個子問題，移動 n － 1 個金盤的問題還可以變成移動 n － 2 個金盤的問題，同樣可變成移動 n － 3 ，…， 1 個金盤的問題，從而將整個問題加以解決。
這三個步驟就是解決問題的通式，可以以過程的形式把它們定義下來：
hanoi(n － 1,s,o,i)
move(s,n,o)
hanoi(n － 1,i,s,o)
參考程序如下：
declare sub hanoi(n,s,i,o)
declare sub move(s,n,o)
input "How many disks?",n
s ＝ 1
i ＝ 2
o ＝ 3
call hanoi(n,s,i,o)
end
sub hanoi(n,s,i,o)
rem 遞歸子程序
if n ＝ 1 then
call move(s,1,o)
else
call hanoi(n － 1,s,o,i)
call move(s,n,o)
call hanoi(n － 1,i,s,o)
endif
end sub
sub move(s,n,o)
print "move disk";n;
print "from";s;"to";o
end sub

H. 關於遞歸

1、調用子程序的含義：
在過程和函數的學習中，我們知道調用子程序的一般形式是：主程序調用子程序A，子程序A調用子程序B，如圖如示，這個過程實際上是：

＠當主程序執行到調用子程序A語句時，系統保存一些必要的現場數據，然後執行類似於BASIC語言的GOTO語句，跳轉到子程序A（為了說得簡單些，我這里忽略了參數傳遞這個過程）。
＠當子程序A執行到調用子程序B語句時，系統作法如上，跳轉到子程序B。
＠子程序B執行完所有語句後，跳轉回子程序A調用子程序B語句的下一條語句（我這又忽略了返回值處理）
＠子程序A執行完後，跳轉回主程序調用子程序A語句的下一條語句
＠主程序執行到結束。
做個比較：我在吃飯（執行主程序）吃到一半時，某人叫我（執行子程序A），話正說到一半，電話又響了起來（執行子程序B），我只要先接完電話，再和某人把話說完，最後把飯吃完（我這飯吃得也夠累的了J）。
2、認識遞歸函數
我們在高中時都學過數學歸納法，例：
求 n！
我們可以把n！這么定義

也就是說要求3！，我們必須先求出2！，要求2！，必須先求1！，要求1！，就必須先求0！，而0!=1，所以1!=0!*1=1，再進而求2!，3!。分別用函數表示，則如圖：

我們可以觀察到，除計算0！子程序外，其他的子程序基本相似，我們可以設計這么一個子程序：
int factorial(int i){
int res;
res=factorial(I-1)*i;
return res;
}
那麼當執行主程序語句s=factorial(3)時，就會執行factorial(3),但在執行factorial(3)，又會調用factorial(2)，這時大家要注意，factorial(3)和factorial(2)雖然是同一個代碼段，但在內存中它的數據區是兩份！而執行factorial(2)時又會調用factorial（1），執行factorial（1）時又會調用factorial（0），每調用一次factorial函數，它就會在內存中新增一個數據區，那麼這些復制了多份的函數大家可以把它看成是多個不同名的函數來理解；
但我們這個函數有點問題，在執行factorial（0）時，它又會調用factorial（－1）。。。造成死循環，也就是說，在factorial函數中，我們要在適當的時候保證不再調用該函數，也就是不執行res=factorial(I-1)*i;這條調用語句。所以函數要改成：
int factorial(int i){
int res;
if (I>0) res=factorial(I-1)*i; else res=1;
return res;
}
那麼求3!的實際執行過程如圖所示：

3、如何考慮用遞歸的方法來解決問題
例：求s=1+2+3+4+5+6+……+n
本來這個問題我們過去常用循環累加的方法。而這里如要用遞歸的方法，必須考慮兩點：
1） 能否把問題轉化成遞歸形式的描述；
2） 是否有遞歸結束的邊界條件。
設:函數s(n)=1+2+3+…+(n-1)+n
顯然遞歸的兩個條件都有了：
1） s(n) =s(n-1)+n
2） s(1)=1
所以源程序為：
int progression(int n){
int res;
if (n=1 )res=1 else res=progression(n-1)+n;
return res;
}
4、遞歸的應用
中序遍歷二叉樹
void inorder (BinTree T){
if (T){
inorder(T->lchild);
printf(「%c」,T->data);
inorder(T->rchild);
}
}
現假設樹如圖（為了講解方便，樹很簡單）

＠執行第一次調用inorder1，T指向頂結點，T不為空，所以第二次調用inorder2；
＠T指向頂結點的左子樹結點也就是B，不為空，所以第三次調用inorder3；
＠T指向B結點的左子樹結點，為空，所以什麼都不執行，返回inorder2；
＠列印B結點的DATA域值「b」；
＠第四次調用inorder4，去訪問B子樹的右結點
＠T指向B結點的右子樹結點，為空，所以什麼都不執行，返回inorder2；
＠返回inorder1；
＠列印A結點的DATA域值「a」；
＠第五次調用inorder5，去訪問A子樹的右結點；
＠T指向A結點的右子樹結點，為空，所以什麼都不執行，返回inorder1；
＠inorder1執行完畢，返回。

I. 解遞歸方程的三個方法

1、主方法求解遞歸式

一種求解大部分遞歸式的公式。給出遞歸式: T(n) = a * T(n/b) + f(n) ，其中a>=1，b>1，f(n)是給定的函數，T(n)是定義在非負整數上的遞歸式。

2、遞歸樹求解

用主方法求解不了的遞歸式，我們可以用遞歸樹來猜測解的上界，然後用代入法來證明解的正確性。遞歸樹的求解精確度取決於畫遞歸樹的精確度。

3、代入法

比如我們求解，遞歸式T(n) = 2T(n/2)+n，我們猜測解是O(nlgn)，我們要尋找到一個常數c，使得T(n)<=cnlgn。

即T(n) <= 2c(n/2)lg(n/2)+n <= cnlgn-cnlg2+n = cnlgn-cn+n

只要c>=1，T(n)<=cnlgn，所以我們的猜測是正確的。

要注意的是，代入法全憑經驗，通常用遞歸樹來確定上界，然後用代入法再證明。

(9)遞歸的受理方法和技巧擴展閱讀：

設p0，p1，…，pn，…是一個序列。如果pn和序列中在它前面的若干項聯系起來的一個關系式對所有大於等於某個整數n0的整數n都是有效的，則稱這個關系式為遞歸關系(recursive relation)式。

如：設(a0，a1，...，ar，...)是一個序列，把該序列中的ar和它前面的幾個ai(0≤i<r)關聯起來的方程稱做一個遞歸關系。如關系式:ar=3ar-1(r≥1)和錯排數:Dn=(n-1)(Dn-1+Dn-2) (n=3，4，...)，都是遞歸關系。

J. 什麼情況下可以利用遞歸來解決問題再寫遞歸程序時應注意是什麼

比如階乘，也就是說求n可以先求n-1，以此類推，到1，這類問題都可以用遞歸解決，菲波拉鍥數也可以遞歸。因為遞歸是總是調用自身解決問題，所以，必須有結束條件，否則會出問題，導致內存卡爆