Recursive | 牛的大腦

recursive(遞迴)
簡潔易懂,但效率差,適合描述演算法
可分為以下3種:
direct recursion:直接呼叫自己
indirect recursion:先呼叫其它程序若干層後,最後又呼叫回自己
tail recursion:在最後一個命令又呼叫自己本身(由於尾端遞迴的返回位址是程式的結束指令,即時返回也不需進行處理)
若把此改掉,可以不需要儲存返回位址與程式狀態,而能夠提昇執行效率

遞迴函數=基本元素+建立其他新元素所需規則
遞迴演算法=遞迴關係+終止條件(需有一條路徑不再進行遞迴呼叫)
(若無法到達終止條件會造成無窮迴窮)

分析遞迴複雜度的工具:
遞迴樹:用樹狀結構表示遞迴的呼叫情況
遞迴關係式=用關係式表示呼叫遞迴的關係

當遞迴關係式可表示成為:
T(n)=aT(n/b)+cn^k,a與b=整數常數,c與k為正常數,a>=1,b>=2,在比較a,b^k大小關係,可以得到:
T(n)={
　O(n^logb(a)),if a< b^k
　O(n^k log n),if a=b^k
　O(n^k),if a< b^k

removal of recursion 遞迴轉成非遞迴
1堆疊法:indirect recursion和direct recursion處理稍有不同
2folding(折疊法)

……………..

fibonacci(費氏數列) O(2^n)
遞回迴關係式:t(n){0,if n=0; 1,if n=1; t(n-1)+t(n-2)+c,otherwise
推導過程:t(n-1)+t(n-2)+c=t(t(n-2)+t(n-3)+c)+t(t(n-3)+t(n-4)+c)+c=…2^(n-1)*t(1)+(2^(n-1)-1)*c
所以t(n)=(2^n-1)*c > big O(2^n)

int fibonacci(int n){
　if(n=0)return (0);
　else if(n=1)return (1);
　else return(fibonacci(n-1)+fibonacci(n-2));
}
int fibonacci(int n){
　int fib_n,fib_n_1,fib_n_2;
　if(n==0)return(0);
　else if(n==1)return(1);
　else{
　　fib_n_2=0;fib_n_1=1;
　　for(i=2;i<=n;i++){
　　　fib_n=fib_n_1+fib_n_2; fib_n_1=fib_n_2; fib_n_2=fib_n;
　　}
　return(fib_n);
　}
}

hanoi(河內塔問題) O(2^n)
遞迴關係式:T(n){
2T(n-1)+c ,n>=2 where c屬於constant(遞迴關係)
c ,n=1 where c屬於constant(終止條件)
推導…
ps:搬動n個套環需2^n-1次

bin_search(二元搜尋),O(2底log n)
遞迴關係式:T(n)={
T(n/2)+c ,n>=2 where c屬於constant(遞迴關係)
c , n=1 where c屬於constant(終止條件)

最大/最小問題,O(n)
遞迴關係式:T(n)={
2T(n/2)+c ,n>=2 where c屬於constant(遞迴關係)
c , n=1 where c屬於constant(終止條件)

選擇問題 O(n^2)

矩陣乘法問題 O(n^3)
遞迴關係式,推導…

volker strassen O(n^2.81)
遞迴關係式,推導…

…

//找總數
int findsum(int n){ //1+2+…n
　if(n==1)return(1); //終止條件
　else return(findsum(n-1)+n); //遞迴條件
}
int findsum(int n){
　int result,i;
　for(i=n;i>1;i++){result+=i;}
　return result;
}

//找最大,尚未測試
int findmax(int a[],int max,int i){ //find(a,1,陣列元素);
　if(i==0){return max}
　else{
　　if(max < a[i] )max=a[i];
　　findmax(a,max,i-1);
　}
}

//找最大公因數

int findgcd(int x,int y){
　return((y==0)?x:findgcd(y,x%y))
}
int findgcd(int x,y){
　if(y==0)return(x);
　else return(findgcd(y,x%y));
}
int findgcd(int x,y){
int remainder=x%y;
　while(remainder!=0){
　　x=y;y=remainder;
　　remainder=x%y;
　}
　return(y);
}

找一字串的所有排列

void permutation(char list[],int i,int n){
　int j,temp;
　if(i==n){ printf("%s",list);}
　else{
　　for(j=i;j<=n;j++){
　　　swap(list[i],list[j],temp);
　　　permutation(list,i+1,n);
　　　swap(list[i],list[j],temp);
　　}
　}
}
t(n)={c ,if n=1; n*t(n-1)+c*n ,if n>=2;
t(n)=n*t(n-1)+c*n=n*t((n-1)*t((n-1)-1)+c*(n-1))+c*n=(n*(n-1))*t(n-2)+c*(n+(n-1))=.....=O(n!)

ackermann
……

分享此文：