A. 一個遞歸演算法必須包括什麼
一個遞歸演算法必須包括終止條件和遞歸部分。
一般循環就是:
int multi = 1;
if (x <=1) return (1);
for(int i=1;i<=x;i++)multi = multi*i;
return(multi);
遞歸把x!看作x*(x-1)!
int multi(int x){if(x==0||x==1) return 1;else return x*multi(x-1);}
尾部遞歸:
而不對其再加運算。尾部遞歸與循環是等價的,而且在一些語言(如Scheme中)可以被優化為循環指令。
在這些語言中尾部遞歸不會佔用調用堆棧空間。以下Scheme程序同樣計算一個數字的階乘,但是使用尾部遞歸:(define(factorialn)(define(iterproctcounter)(if(>countern)proct(iter(*counterproct)(+counter1))))(iter11))。
B. java中遞歸演算法是什麼怎麼算的
Java遞歸演算法是基於Java語言實現的遞歸演算法。遞歸演算法是一種直接或者間接調用自身函數或者方法的演算法。遞歸演算法實質是把問題分解成規模縮小的同類問題的子問題,然後遞歸調用方法表示問題的解。遞歸往往能給我們帶來非常簡潔非常直觀的代碼形式,從而使我們的編碼大大簡化,然而遞歸的思維確實跟我們的常規思維相逆的,通常都是從上而下的思維問題,而遞歸趨勢從下往上的進行思維。
二、遞歸演算法解決問題的特點:
【1】遞歸就是方法里調用自身。
【2】在使用遞歸策略時,必須有一個明確的遞歸結束條件,稱為遞歸出口。
【3】遞歸演算法代碼顯得很簡潔,但遞歸演算法解題的運行效率較低。所以不提倡用遞歸設計程序。
【4】在遞歸調用的過程中系統為每一層的返回點、局部量等開辟了棧來存儲。遞歸次數過多容易造成棧溢出等,所以一般不提倡用遞歸演算法設計程序。
【5】在做遞歸演算法的時候,一定把握出口,也就是做遞歸演算法必須要有一個明確的遞歸結束條件。這一點是非常重要的。其實這個出口就是一個條件,當滿足了這個條件的時候我們就不再遞歸了。
三、代碼示例:
代碼執行流程圖如下:
此程序中n=5就是程序的出口。
C. 遞歸演算法
遞歸演算法
遞歸演算法流程
遞歸過程一般通過函數或子過程來實現。遞歸演算法:在函數或子過程的內部,直接或者間接地調用自己的演算法。
遞歸演算法的特點
遞歸演算法是一種直接或者間接地調用自身的演算法。在計算機編寫程序中,遞歸演算法對解決一大類問題是十分有效的,它往往使演算法的描述簡潔而且易於理解。 遞歸演算法解決問題的特點: (1) 遞歸就是在過程或函數里調用自身。 (2) 在使用遞歸策略時,必須有一個明確的遞歸結束條件,稱為遞歸出口。 (3) 遞歸演算法解題通常顯得很簡潔,但遞歸演算法解題的運行效率較低。所以一般不提倡用遞歸演算法設計程序。 (4) 在遞歸調用的過程當中系統為每一層的返回點、局部量等開辟了棧來存儲。遞歸次數過多容易造成棧溢出等。所以一般不提倡用遞歸演算法設計程序。
遞歸演算法要求
遞歸演算法所體現的「重復」一般有三個要求: 一是每次調用在規模上都有所縮小(通常是減半); 二是相鄰兩次重復之間有緊密的聯系,前一次要為後一次做准備(通常前一次的輸出就作為後一次的輸入); 三是在問題的規模極小時必須用直接給出解答而不再進行遞歸調用,因而每次遞歸調用都是有條件的(以規模未達到直接解答的大小為條件),無條件遞歸調用將會成為死循環而不能正常結束。
舉例
描述:把一個整數按n(2<=n<=20)進製表示出來,並保存在給定字元串中。比如121用二進製表示得到結果為:「1111001」。 參數說明:s: 保存轉換後得到的結果。 n: 待轉換的整數。 b: n進制(2<=n<=20) void numbconv(char *s, int n, int b) { int len; if(n == 0) { strcpy(s, ""); return; } /* figure out first n-1 digits */ numbconv(s, n/b, b); /* add last digit */ len = strlen(s); s[len] = ""[n%b]; s[len+1] = '\0'; } void main(void) { char s[20]; int i, base; FILE *fin, *fout; fin = fopen("palsquare.in", "r"); fout = fopen("palsquare.out", "w"); assert(fin != NULL && fout != NULL); fscanf(fin, "%d", &base); /*PLS set START and END*/ for(i=START; i <= END; i++) { numbconv(s, i*i, base); fprintf(fout, "%s\n", s); } exit(0); }
編輯本段遞歸演算法簡析(PASCAL語言)
遞歸是計算機科學的一個重要概念,遞歸的方法是程序設計中有效的方法,採用遞歸編寫 程序能是程序變得簡潔和清晰.
一 遞歸的概念
1.概念 一個過程(或函數)直接或間接調用自己本身,這種過程(或函數)叫遞歸過程(或函數). 如: procere a; begin . . . a; . . . end; 這種方式是直接調用. 又如: procere c(形參);forward; procere b; 局部說明 begin . . c(實參); . . end; procere c; 局部說明; begin . . b; . . end; 這種方式是間接調用. 例1計算n!可用遞歸公式如下: fac:=n*fac(n-1) {當n>0時} fac(n)={ fac:=1; { 當n=0時} 可編寫程序如下: program facn; var n:integer; function fac(n:integer):real; begin if n=0 then fac:=1 else fac:=n*fac(n-1); end; begin write('n=');readln(n); writeln(n,'!=',fac(n):0:0); end. 例2 樓梯有n階台階,上樓可以一步上1階,也可以一步上2階,編一程序計算共有多少種不同的走法. 設n階台階的走法數為f(n) 顯然有 n=1 f(n)={ f(n-1)+f(n-2) n>2 可編程序如下: program louti; var n:integer; function f(x:integer):integer; begin if x=1 then f:=1 else if x=2 then f:=2 else f:=f(x-1)+f(x-2); end; begin write('n=');read(n); writeln('f(',n,')=',f(n)) end.
二 如何設計遞歸演算法
1.確定遞歸公式 2.確定邊界(終了)條件
三 典型例題
例3 漢諾塔問題 如圖:已知有三根針分別用1,2,3表示,在一號針中從小放n個盤子,現要求把所有的盤子 從1針全部移到3針,移動規則是:使用2針作為過度針,每次只移動一塊盤子,且每根針上 不能出現大盤壓小盤.找出移動次數最小的方案. 程序如下: program hanoi; var n:integer; procere move(n,a,b,c:integer); begin if n=1 then writeln(a,'->',c) else begin move(n-1,a,c,b); writeln(a,'--->',c); move(n-1,b,a,c); end; end; begin write('Enter n='); read(n); move(n,1,2,3); end. 例4 快速排序 快速排序的思想是:先從數據序列中選一個元素,並將序列中所有比該元素小的元素都放到它的右邊或左邊,再對左右兩邊分別用同樣的方法處之直到每一個待處理的序列的長度為1, 處理結束. 程序如下: program kspv; const n=7; type arr=array[1..n] of integer; var a:arr; i:integer; procere quicksort(var b:arr; s,t:integer); var i,j,x,t1:integer; begin i:=s;j:=t;x:=b ; repeat while (b[j]>=x) and (j>i) do j:=j-1; if j>i then begin t1:=b; b:=b[j];b[j]:=t1;end; while (b<=x) and (i<j) do i:=i+1; if i<j then begin t1:=b[j];b[j]:=b;b:=t1; end until i=j; b:=x; i:=i+1;j:=j-1; if s<j then quicksort(b,s,j); if i<t then quicksort(b,i,t); end; begin write('input data:'); for i:=1 to n do read(a); writeln; quicksort(a,1,n); write('output data:'); for i:=1 to n do write(a:6); writeln; end.
編輯本段{遞歸的一般模式}
procere aaa(k:integer); begin if k=1 then (邊界條件及必要操作) else begin aaa(k-1); (重復的操作); end; end;
開放分類:
編程,計算機,演算法
引自:http://ke..com/view/1733593.htm
D. 易語言遞歸演算法怎麼用,求高手給舉個簡單點的例子
遞歸,簡單說是子程序自己調用自己。
例子:
.版本 2
.子程序 左右查找
.參數 左邊值, 整數型
.參數 右邊值, 整數型
.參數 查找數組, , 數組
.參數 ww, , 參考 可空 數組
.局部變數 i, 整數型
.局部變數 j, 整數型
.局部變數 中間值, 整數型
.如果真 (左邊值 ≥ 右邊值)
返回 ()
.如果真結束
i = 左邊值
j = 右邊值
.判斷循環首 (j ≠ i)
.判斷循環首 (查找數組 [左邊值] ≤ 查找數組 [j] 且 i < j)
j = j - 1
.判斷循環尾 ()
.判斷循環首 (查找數組 [左邊值] ≥ 查找數組 [i] 且 i < j)
i = i + 1
.判斷循環尾 ()
.如果真 (i < j)
中間值 = 查找數組 [j]
查找數組 [j] = 查找數組 [i]
查找數組 [i] = 中間值
.如果真結束
.判斷循環尾 ()
中間值 = 查找數組 [左邊值]
查找數組 [左邊值] = 查找數組 [i]
查找數組 [i] = 中間值
左右查找 (左邊值, i - 1, 查找數組, ) ' 繼續處理左邊的,這里是個遞歸的過程
左右查找 (i + 1, 右邊值, 查找數組, ) ' 繼續處理右邊的,這里是個遞歸的過程
ww = 查找數組
' 以上是快速排序的代碼實現,核心所在是遞歸的過程。
E. 遞歸演算法是什麼
遞歸演算法(英語:recursion algorithm)在計算機科學中是指一種通過重復將問題分解為同類的子問題而解決問題的方法。
遞歸式方法可以被用於解決很多的計算機科學問題,因此它是計算機科學中十分重要的一個概念。絕大多數編程語言支持函數的自調用,在這些語言中函數可以通過調用自身來進行遞歸。
計算理論可以證明遞歸的作用可以完全取代循環,因此在很多函數編程語言(如Scheme)中謹段習慣用遞歸來實現循環。