遞歸演算法探究論文

A. 遞歸演算法的介紹

遞歸演算法是把問題轉化為規模縮小了的同類問題的子問題。然後遞歸調用函數（或過程）來表示問題的解。一個過程(或函數)直接或間接調用自己本身,這種過程(或函數)叫遞歸過程(或函數).

B. 什麼是遞歸演算法

遞歸做為一種演算法在程序設計語言中廣泛應用.是指函數/過程/子程序在運行過程序中直接或間接調用自身而產生的重入現像.

程序調用自身的編程技巧稱為遞歸（ recursion）。
一個過程或函數在其定義或說明中又直接或間接調用自身的一種方法，它通常把一個大型復雜的問題層層轉化為一個與原問題相似的規模較小的問題來求解，遞歸策略只需少量的程序就可描述出解題過程所需要的多次重復計算，大大地減少了程序的代碼量。遞歸的能力在於用有限的語句來定義對象的無限集合。用遞歸思想寫出的程序往往十分簡潔易懂。
一般來說，遞歸需要有邊界條件、遞歸前進段和遞歸返回段。當邊界條件不滿足時，遞歸前進；當邊界條件滿足時，遞歸返回。
注意：
(1) 遞歸就是在過程或函數里調用自身;
(2) 在使用遞增歸策略時，必須有一個明確的遞歸結束條件，稱為遞歸出口，否則將無限進行下去（死鎖）。

遞歸演算法一般用於解決三類問題：
(1)數據的定義是按遞歸定義的。(Fibonacci函數)
(2)問題解法按遞歸演算法實現。(回溯)
(3)數據的結構形式是按遞歸定義的。(樹的遍歷，圖的搜索)

遞歸的缺點：
遞歸演算法解題的運行效率較低。在遞歸調用的過程當中系統為每一層的返回點、局部量等開辟了棧來存儲。遞歸次數過多容易造成棧溢出等。

C. 遞歸演算法的特性

遞歸演算法兩個特性
1.遞歸演算法是一種分而治之，把復雜問題分解為簡單問題的求解問題方法，對求解某些復雜問題，遞歸演算法的分析方法是有效地。
2遞歸演算法的時間效率低

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

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

E. 遞歸演算法有何特點

遞歸4—遞歸的弱點

之所以沒有把這段歸為演算法的討論，因為這里討論的不在是演算法，而只是討論一下濫用遞歸的不好的一面。

遞歸的用法似乎是很容易的，但是遞歸還是有她的致命弱點，那就是如果運用不恰當，濫用遞歸，程序的運行效率會非常的低，低到什麼程度，低到出乎你的想像！當然，平時的小程序是看不出什麼的，但是一旦在大項目里濫用遞歸，效率問題將引起程序的實用性的大大降低！

例子：求1到200的自然數的和。

第一種做法：

#include <stdio.h>

void main()

{

int i;

int sum=0;

for(i=1;i<=200;i++)

{

sum+=i;

}

printf("%d\n",sum);

}

該代碼中使用變數2個，計算200次。再看下個代碼：

#include <stdio.h>

int add(int i)

{

if(i==1)

{

return i;

}

else

{

return i+add(i-1);

}

}

void main()

{

int i;

int sum=0;

sum=add(200);

printf("%d\n",sum);

}

但看add（）函數，每次調用要聲明一個變數，每次調用要計算一次，所以應該是200個變數，200次計算，對比一下想想，如果程序要求遞歸次數非常多的時候，而且類似與這種情況，我們還能用遞歸去做嗎？這個時候寧願麻煩點去考慮其他辦法，也要嘗試擺脫遞歸的干擾。

21:21 | 添加評論 | 固定鏈接 | 引用通告 (0) | 記錄它 | 計算機與 Internet
程序演算法5—遞歸3—遞歸的再次挖掘

遞歸的魅力就在於遞歸的代碼，寫出來實在是太簡練了，而且能解決很多看起來似乎有規律但是又不是一下子能表達清楚的一些問題。思路清晰了，遞歸一寫出來問題立即就解決了，給人一重感覺，遞歸這么好用。我們在此再更深的挖掘一下遞歸的用法。

之前再強調一點，也許有人會問，你前邊的例子用遞歸似乎是更麻煩了。是，是麻煩了，因為為了方便理解，只能舉一些容易理解的例子，一般等實際應用遞歸的時候，遠遠不是這種狀態。

好了我們現在看一個數字的序列；有一組數的集合{1，2，4，7，11，16，22，29，37，46，56……}我故意多給幾項，一般是只給前4項讓你找規律的。序列給了，要求是求前50項的和。規律？有？還是沒有？一看就象有，但是又看不出來，我多給了幾項，應該很快看出來了，哦，原來每相鄰的兩項的差是個自然數排列，2-1=1，4-2=2，7-4=3，11-7=4，16-11=5……

好了，把規律找出來了，一開始可能覺得沒頭緒，沒問題，咱們把這個序列存放到一個數組總可以吧！那我們就聲明一個數組，存放前50個數據，一個一個相加總可以了。於是有了下邊的寫法：

#include <stdio.h>

void main()

{

int i,a[50],sum=0;

a[0]=1;

for(i=1;i<50;i++)

{

a[i]=a[i-1]+i;

}

for(i=0;i<50;i++)

{

sum+=a[i];

}

printf("%d\n",sum);

}

好了，代碼運行一下，結果出來了，正確不正確呢？自己測試吧，把50項改成1、2、3、4、5……項，試試前多少項是不是正確，雖然這不是正確的測試方法，但是的確是常用的測試方法。

等到這個代碼已經完全理解了，完全明白了正個計算過程，我們就應該對這段代碼進行改寫優化了，畢竟這個代碼還是不值得用一個數組的，那麼我們嘗試著只用變數去做一下：

#include <stdio.h>

void main()

{

int i;

int number=1;

int sum=0;

for(i=0;i<50;i++)

{

number+=i;

sum+=number;

}

printf("%d\n",sum);

}

不知道我這樣寫是不是跨度大了點，但是我不準備詳細解釋了，很多東西需要你去認真分析的，所以很多東西如果不懂，自己想清楚比別人解釋的效果會更好，因為別人講只能讓你理解，如果你自己去想，你就在理解的同時學會了思考。

這個代碼寫出來，不要繼續看下去，先自己嘗試著把這個題目用遞歸做一下看看自己能不能寫出來，當然，遞歸並不是那麼輕松就能使用的，有時候也是需要去細心設計的。如果做出來了，對比一下下邊的代碼，如果沒有寫出來，建議認真分析後邊的代碼，然後最好是能完全掌握，能自己隨時把這行代碼寫出來：

#include <stdio.h>

int add(int n,int num,int i)

{

num+=i;

if(i>=n-1)

{

return num;

}

else

{

return num+add(n,num,i+1);

}

}

void main()

{

int sum;

sum=add(50,1,0); /*50表示前50象項*/

printf("%d\n",sum);

}

當然這個代碼中的n只是一個參考變數，如果把if(i>=n-1)中的n該成50，那麼就不需要這個n了，函數兩個參數就可以了，這樣寫是為了修改方便。

20:28 | 添加評論 | 固定鏈接 | 引用通告 (0) | 記錄它 | 計算機與 Internet
程序演算法4—遞歸2—遞歸的魅力

兩天沒有再寫下去，因為畢竟有時候會有點心情問題，有時候覺得心情不好，一下子什麼東西都想不起來了，很多時候寫一些東西是需要狀態的，一旦狀態有了，想的東西才能順利的寫出來，雖然有些東西寫出來在別人看來很垃圾，但是起碼自己覺得還是相當滿意的，我寫這個本來就沒有多少技術含量，只是想給初學程序的人一些指引，加快他們對程序的領悟！

好了，言歸正傳，繼續上次遞歸的討論，看看遞歸的魅力所在。

有這樣一個問題，說一個猴子和一堆蘋果，猴子一天吃一半，然後再吃一個，10天後剩下一個了，也就是說吃了10次，剩下1個了。問原來一共有多少蘋果。

當然我們的目的不是求出蘋果的數量，而是尋求一種解決問題的方法，這個問題一出來，通常對程序掌握深度不一樣的朋友對這個題會有不同的認識，首先介紹一種解決方法，這種人腦袋還是比較聰明的，思路非常的明確，也有可能語言工具掌握的也不錯，代碼寫出來非常准確，先看一下代碼再做評價吧：

#include <stdio.h>

void main()

{

int day=10;

int apple;

int i,j;

for(i=1;;i++)

{

apple=i;

for(j=0;j<day;j++)

{

if(apple%2==0&&apple>0)

{

apple/=2;

apple--;

}

else

{

break;

}

}

if(j==day&&apple==1)

{

printf("%d\n",i);

return;

}

}

}

程序的大概思路很明確，簡單介紹一下，這種寫法就是從一個蘋果開始算起，for(i=1;;i++)的作用就是改變蘋果的數量，如果1個符合條件，那就試試2個，然後3個、4個一直到適合為止，里邊的for循環就是把每一次取得的蘋果的數目進行計算，如果每次都能順利的被2整除（也就是說每次都能保證猴子能正好吃一半），然後再減一一直到最後，如果最後蘋果剩下是一個而且天數正好是10天，那麼就輸出一下蘋果的數目，整個程序退出，如果看不明白的沒關系，這個寫法非常的不適用，我們叫寫出這種演算法的人傻X，雖然這種人腦袋也挺聰明，能寫出一些新鮮的寫法，但是又臟又臭，代碼既不簡練又不高效。

所以說，有時候有些人以為自己學的很好了，自己所做的一切都是最好的，這種想法是不正確的，也許有些初學者沒有什麼經驗寫出來的代碼卻更讓人容易明白點，那麼也是先看看代碼：

#include <stdio.h>

void main()

{

int day[11];

int i;

day[0]=1;

for(i=1;i<11;i++)

{

day[i]=(day[i-1]+1)*2;

}

printf("%d\n",day[10]);

}

代碼不長，而且也恰當的應用了題目中的規律，不是說要吃一半然後再吃一個嗎？那我用數組來存放每天蘋果的數量，用day[0]表示最後一天的蘋果數量，那就是剩下的一個，然後就是找規律了，什麼規律？就是如果猴子不多吃一個的話，那就是正好吃了一半，也就是說猴子當天吃了之後剩餘的蘋果的數目加1個然後再乘以2就是前一天的數目了，這樣一想這個題目就簡單的多了，於是這個題用數組就輕松的做出來了。

那麼這個代碼究竟是不是已經很好了呢，我們注意到，這里邊每個數組元素只用了一次並沒有被重復使用，再這種情況下我們是不是可以用一種方法代替數組呢？於是就有了更優化的寫法，這個寫法似乎已經是相當簡練了：

#include <stdio.h>

void main()

{

int apple=1;

int i;

for(i=0;i<10;i++)

{

apple=(apple+1)*2;

}

printf("%d\n",apple);

}

代碼寫到這里已經把問題完全抽象化了，所以我們就應該站在數學的角度去分析了。也許我們就應該結束了討論，但是偏偏這個時候，又來了遞歸，悄悄的通過美麗的調用顯示了一下她的魅力：

#include <stdio.h>

int apple(int i)

{

if(i==0)

{

return 1;

}

else

{

return (apple(i-1)+1)*2;

}

}

void main()

{

int i;

i=apple(10);

printf("%d\n",i);

}

原理都還是一樣的，但是寫出來的格式已經完全變掉了，沒有了for循環。假想一個復雜的問題遠比這個問題復雜，而且沒有固定循環次數，那麼我們再使用循環雖然也能解決問題，但是可能面臨循環難以設計、控制等問題，這個時候用遞歸可能就會讓問題變的非常的清晰。

另外說一點，一般我這里的代碼，並不是從最差到最好的，基本排列是從最差到最合適的代碼（當然是本人認為最合適的，也許還有更好的，本人能力所限了），然後最後給出一種比較違反常規的代碼，一般是不贊成用最後一種代碼的，當然有時候最後一種代碼也許是最好的選擇，看情況吧！

20:25 | 添加評論 | 固定鏈接 | 引用通告 (0) | 記錄它 | 計算機與 Internet
10月15日
程序演算法3—遞歸1—遞歸小顯威力

現在用C語言實現一個字元串的倒序輸出，當然，方法也是很多的，但是如果程序中能有相對優化的方法或者簡單明了易讀的方法，那對你自己或者別人都是一種幸福。

第一種寫法，這類寫法既浪費內存又不實用，一般是剛學程序的才這樣做，程序的結構很簡單，利用的是數組：

#include <stdio.h>

void main()

{

char c[2000];

int i,length=0;

for(i=0;i<2000;i++)

{

scanf("%c",&c[i]);

if(c[i]=='\n')

{

break;

}

else

{

length++;

}

}

for(i=length;i>0;i--)

{

printf("%c",c[i-1]);

}

printf("\n");

}

這段代碼中的數組，聲明大了浪費內存空間，聲明小了又怕不夠，所以寫這種代碼的人一般寫完之後會祈禱，祈禱測試的人不要輸入的太多，太多就不能完全顯示了！

與其這么提心吊膽，於是又有人想出了第二種方法，終於解決了一些問題，而且完全實現了程序的實際要求，於是，這種人經過一番苦想，覺得問題終於可以解決了，這種方法看起來是一種很不錯的方法。

#include <stdio.h>

#include <malloc.h>

void main()

{

int i;

char *c;

c=(char *)malloc(1*sizeof(char));

for(i=0;;i++)

{

*(c+i)=getchar();

if(*(c+i)=='\n')

{

*(c+i)='\0';

break;

}

else

c=(char *)realloc(c,(i+2)*sizeof(char));

}

for(--i;i>=0;i--)

{

putchar(*(c+i));

}

printf("\n");

free(c);

}

怎麼樣？不錯，准確的應用內存，幾乎沒有浪費什麼空間，這種方法也體現了一下指針的強大功能，寫這個程序雖然不敢說這個人已經掌握了指針的應用，但是起碼可以說他已經會用指針了。代碼寫出來，看起來已經有點美感。

但是也有一些人還是比較喜歡動腦筋的，經過一番思考，終於想出了第三種比較容易寫的方法，也許有寫初學者可能覺得有些難度，但是事實上這個東西一點都不難，如果稍微有點程序功底之後再看這段代碼，應該是相當輕松！

#include <stdio.h>

void run()

{

char c;

c=getchar();

if(c!='\n')

{

run();

}

else

{

return;

}

putchar(c);

}

void main()

{

run();

printf("\n");

}

寫出的代碼讓人眼前一亮，哇！原來遞歸功能簡單而又好用，那我們為什麼不好好利用呢？但是遞歸也不一定就是最好的選擇，因為有時候雖然遞歸用起來很方便，但是效率卻不高，以後的討論中還會詳細說明。

F. 關於《中序遍歷二叉樹的非遞歸演算法》的論文

實用《數據結構》編程——二叉樹的建立、中序遍歷非遞歸C程序 宋麗敏 <正>近年來,伴隨著計算機應用技術的快速發展,系統程序和應用程序的規模越來越大,應用領域越來越廣泛.計算機的應用已不再局限於科學計算,而更多地應用於控制、管理及數據處理等非數值計算的處理工作.需要通過計算機加工、處理的數據對象也日益復雜化.《數據結構》課程就是一門以這些復雜的非數值型數據為研究對象,研【作者單位】：河北省廊坊職業技術學院(西校區) 065000【分類號】：G634.6【DOI】：cnki:ISSN:1005-9741.0.2004-02-009【正文快照】：近年來,伴隨著計算機應用技術的快速發展,系統程序和應用程序的規模越來越大,應用領域越來越廣泛.計算機的應用已不再局限於科學計算,而更多地應用於控制、管理及數據處理等非數值計算的處理工作.需要通過計算機加工、處理的數據對象也日益復雜化.《數據結構》課程就是一門以這 …… http://www.cnki.com.cn/Article/CJFDTotal-LKJX200402009.htm

G. 什麼是遞歸演算法

遞歸演算法就是一個函數通過不斷對自己的調用而求得最終結果的一種思維巧妙但是開銷很大的演算法。
比如：
漢諾塔的遞歸演算法：
void move(char x,char y){
printf("%c-->%c\n",x,y);
}

void hanoi(int n,char one,char two,char three){
/*將n個盤從one座藉助two座，移到three座*/
if(n==1) move(one,three);
else{
hanoi(n-1,one,three,two);
move(one,three);
hanoi(n-1,two,one,three);
}
}

main(){
int n;
printf("input the number of diskes:");
scanf("%d",&n);
printf("The step to moving %3d diskes:\n",n);
hanoi(n,'A','B','C');
}
我說下遞歸的理解方法
首先：對於遞歸這一類函數，你不要糾結於他是干什麼的，只要知道他的一個模糊功能是什麼就行，等於把他想像成一個能實現某項功能的黑盒子，而不去管它的內部操作先，好，我們來看下漢諾塔是怎麼樣解決的
首先按我上面說的把遞歸函數想像成某個功能的黑盒子，void hanoi(int n,char one,char two,char three); 這個遞歸函數的功能是：能將n個由小到大放置的小長方形從one 位置，經過two位置 移動到three位置。那麼你的主程序要解決的問題是要將m個的"漢諾塊"由A藉助B移動到C，根據我們上面說的漢諾塔的功能，我相信傻子也知道在主函數中寫道：hanoi(m,A,B,C)就能實現將m個塊由A藉助B碼放到C，對吧？所以，mian函數裡面有hanoi(m,'A','C','B');這個調用。
接下來我們看看要實現hannoi的這個功能，hannoi函數應該幹些什麼？
在hannoi函數里有這么三行
hanoi(n-1,one,three,two);
move(one,three);
hanoi(n-1,two,one,three);
同樣以黑盒子的思想看待他，要想把n個塊由A經過B搬到C去，是不是可以分為上面三步呢？
這三部是：第一步將除了最後最長的那一塊以外的n-1塊由one位置經由three搬到two 也就是從A由C搬到B 然後把最下面最長那一塊用move函數把他從A直接搬到C 完事後 第三步再次將剛剛的n-1塊藉助hannoi函數的功能從B由A搬回到C 這樣的三步實習了n塊由A經過B到C這樣一個功能，同樣你不用糾結於hanoi函數到底如何實現這個功能的，只要知道他有這么一個神奇的功能就行
最後：遞歸都有收尾的時候對吧，收尾就是當只有一塊的時候漢諾塔怎麼個玩法呢？很簡單吧，直接把那一塊有Amove到C我們就完成了，所以hanoni這個函數最後還要加上 if(n==1)move(one,three);（當只有一塊時，直接有Amove到C位置就行）這么一個條件就能實現hanoin函數n>=1時將n個塊由A經由B搬到C的完整功能了。
遞歸這個復雜的思想就是這樣簡單解決的，呵呵 不知道你看懂沒？純手打，希望能幫你理解遞歸
總結起來就是不要管遞歸的具體實現細節步驟，只要知道他的功能是什麼，然後利用他自己的功能通過調用他自己去解決自己的功能（好繞口啊，日）最後加上一個極限情況的條件即可，比如上面說的1個的情況。

H. 怎們理解遞歸演算法

先不要往裡想，越想越亂，先想好遞歸結束（最終返回）的條件，然後通過調用自己每次都將問題簡化，這樣說問題可能比較抽象，你看看數據結構書中關於樹的部分，那裡遞歸比較多，而且很多遞歸都不難，比如前序 中序 後序遍歷，找些課本上的程序，用一些簡單的樹為例子一步步走一下，相信你會更清晰的

I. 編寫一個遞歸演算法計算並返回一個鏈表的長度

如果是不帶頭結點的:

public int length(LNode ln){
if(ln==null){
return 0;
}
return 1+length(ln.getNext());
}

J. 用遞歸演算法解決問題

遞歸函數通常用來解決結構自相似的問題。所謂結構自相似，是指構成原問題的子問題與原問題在結構上相似，可以用類似的方法解決。具體地，整個問題的解決，可以分為兩部分：第一部分是一些特殊情況，有直接的解法；第二部分與原問題相似，但比原問題的規模小。實際上，遞歸是把一個不能或不好解決的大問題轉化為一個或幾個小問題，再把這些小問題進一步分解成更小的問題，直至每個小問題都可以直接解決。因此，遞歸有兩個基本要素：
（1）邊界條件：確定遞歸到何時終止，也稱為遞歸出口。
（2）遞歸模式：大問題是如何分解為小問題的，也稱為遞歸體。遞歸函數只有具備了這兩個要素，才能在有限次計算後得出結果。
遞歸就是某個函數直接或間接地調用了自身，這種調用方式叫做遞歸調用。說白了，還是函數調用。既然是函數調用，那麼就有一個雷打不動的原則：所有被調用的函數都將創建一個副本，各自為調用者服務，而不受其他函數的影響。