演算法课程AlgorithmsCourse2递回Recursion课件.ppt

演算法課程演算法課程演算法課程演算法課程 (Algorithms)(Algorithms)Course 2遞迴遞迴Recursion Outlinesu本章重點nDef.與種類nRecursion與Non-recursion的比較n設計方式n遞迴演算法則的複雜度分析數學解法數學解法數學解法數學解法 (Mathematics-based method)(Mathematics-based method)替代法替代法替代法替代法 (Substitution method)(Substitution method)遞迴樹法遞迴樹法遞迴樹法遞迴樹法 (Recursion tree method)(Recursion tree method)支配定理法支配定理法支配定理法支配定理法 (Master theorem method)(Master theorem method)2 Recursion Algorithmu一般來說，有兩種方式可以撰寫具有重覆執行(Repetitive)特性的演算法:n nIteration(Iteration(迴圈迴圈迴圈迴圈)n nRecursion(Recursion(遞迴遞迴遞迴遞迴)uuDefDef:algorithm 中含有self-callingself-calling(自我呼叫)敘述存在。

3u遞迴的種類:n n直接遞迴直接遞迴直接遞迴直接遞迴 (Direct Recursion):(Direct Recursion):函式或程序直接呼叫本身直接呼叫本身直接呼叫本身直接呼叫本身時稱之n n間接遞迴間接遞迴間接遞迴間接遞迴 (Indirect Recursion):(Indirect Recursion):函式或程序先呼叫另外的函式，再從另外函式呼叫原來的函式稱之void Function2(void).Function2();.void Function1(void).Function2();.void Function2(void).Function1();.4n n尾端遞迴尾端遞迴尾端遞迴尾端遞迴 (Tail Recursion):(Tail Recursion):屬於直接遞迴的特例u建議：用非遞迴非遞迴非遞迴非遞迴方式會較有效率n即:改用迴圈迴圈迴圈迴圈(while,repeatuntil)n遞迴要花費額外的處理(如:stack的push,pop,)void Function2(void).Function2();程式結束程式結束程式結束程式結束的前一行的前一行的前一行的前一行5 遞迴演算法則的設計遞迴演算法則的設計1.找出問題的終止條件終止條件終止條件終止條件 (即：即：base case)base case).2.找出問題本身的遞迴關係遞迴關係遞迴關係遞迴關係 (即：即：general case)general case).u遞迴的架構:Procedure 遞迴副程式名遞迴副程式名遞迴副程式名遞迴副程式名(參數)if(base case)return(結果);/達到終止條件時達到終止條件時結束遞迴結束遞迴結束遞迴結束遞迴，需要時回傳結果，需要時回傳結果 else general case;/利用利用general case執行遞迴呼叫執行遞迴呼叫執行遞迴呼叫執行遞迴呼叫，需要時加上，需要時加上return6階乘階乘(Factorial;n!)We can define終止條件終止條件終止條件終止條件遞迴關係遞迴關係遞迴關係遞迴關係7Recursive Factorial Algorithminputsinputs:n is the number being raised factoriallyoutputsoutputs:n!is returnedProcedure Factorial(int n)begin if(n=0)return 1;else return(n Factorial(n-1);end8Write a program in C+int Factorial(int n)if(n=0)return(1);else return(n*Factorial(n-1);9Iterative Factorial Algorithminputsinputs:n is the number being raised factoriallyoutputsoutputs:n!is returnedvoid Factorial(int n)factN=1;for(i=1,i n,i+)for(i=1,i n,i+)factNfactN=factNfactN*i;*i;return factN;10費氏數費氏數(Fibonacci Number)uEx:u觀念:F0+F1 F2 F1 +F2 F3 F2 +F3 F4 F3 +F4 F5n012345678910Fn011235813213455 F Fa a+F Fb b F Fc c11uRecursive Algorithm Definition終止條件終止條件終止條件終止條件遞迴關係遞迴關係遞迴關係遞迴關係12Recursive Fibonacci Algorithminputsinputs:num identified the ordinal of the Fibonacci numberoutputsoutputs:returns the nth Fibonacci numbervoid Fib(int num)if(num is 0 OR num is 1)return num;else return(Fib(num-1)+Fib(num-2);13uBased on recursive function,求Fib(4)共呼叫此函數幾次?(含Fib(4)Ans:9 9次次次次14Iterative Fibonacci Number Algorithminputsinputs:num identified the ordinal of the Fibonacci numberoutputsoutputs:returns the nth Fibonacci numbervoid Fib(int num)if(num is 0 OR num is 1)return num;else F Fa a=0,=0,F Fb b=1;=1;for(ifor(i=2,i=num,i+)=2,i=num,i+)F Fc c=F Fa a+F Fb b;F Fa a=F Fb b;F Fb b=F Fc c;end for;end for;return return F Fc c;C+Program:C+Program:int Fib(int n)if(n=1)return n;else intint FaFa=0,=0,FbFb=1,=1,FcFc,i;,i;for(ifor(i=2;i=n;i+)=2;i=n;i+)FcFc=FaFa+FbFb;FaFa=FbFb;FbFb=FcFc;return return FcFc;15void Function2(void).End;How Recursion Worksvoid Function1(void).Function2();.參數參數參數參數變數變數變數變數位址位址位址位址StackPushPop16要保存保存保存保存Function1Function1當時執行的狀況當時執行的狀況當時執行的狀況當時執行的狀況，即Push下列資料到Stack中。

n n參數值參數值參數值參數值 (Parameter)(Parameter)n n區域區域區域區域/暫存變數值暫存變數值暫存變數值暫存變數值 (Local Variable)(Local Variable)n n返回位址返回位址返回位址返回位址 (Return Address)(Return Address)要做控制權轉移控制權轉移控制權轉移控制權轉移(Jump to Function2)Recursion動作結束時，要Pop StackPop Stack，以取出參數、區域/暫存變數值及返回位址，then goto“Return Address”Push,Jump,Pop皆耗時耗時耗時耗時，效率差效率差效率差效率差uRecursion與Non-recursion的程式可以互相改寫互相改寫互相改寫互相改寫!17 Recursion 與與 Non-recursion 的比較的比較RecursionNon-recursion優優優優u程式較精簡u冗長缺缺缺缺u區域變數極少使用u較多u節省Storage空間u浪費Storageu表達力強，易於理解u表達力差，不易理解缺缺缺缺u需要額外的Dynamic Stack空間支援u不需要優優優優u執行效益較差。

需要花費額外時間做:nPush參數,區域變數,返回位址 in to stackn控制權轉移nPop stacku較優18可自行回答下列問題，若有一個回答為可自行回答下列問題，若有一個回答為可自行回答下列問題，若有一個回答為可自行回答下列問題，若有一個回答為“no”no”，則，則，則，則你不應使用遞迴來設計演算法你不應使用遞迴來設計演算法你不應使用遞迴來設計演算法你不應使用遞迴來設計演算法:1.1.演算法所處理的問題演算法所處理的問題演算法所處理的問題演算法所處理的問題或是或是或是或是資料結構本身資料結構本身資料結構本身資料結構本身合乎遞迴的特性嗎合乎遞迴的特性嗎合乎遞迴的特性嗎合乎遞迴的特性嗎 (Is(Is the algorithm or data structure the algorithm or data structure naturally suited to naturally suited to recursionrecursion)?)?2.2.若用了遞迴是否可使結果若用了遞迴是否可使結果若用了遞迴是否可使結果若用了遞迴是否可使結果更小更小更小更小及及及及更易了解更易了解更易了解更易了解 (Is the recursive Is the recursive solution solution shortershorter and and more understandablemore understandable)?)?3.3.這個遞迴結果的執行是在可接受的這個遞迴結果的執行是在可接受的這個遞迴結果的執行是在可接受的這個遞迴結果的執行是在可接受的執行時間和空間限制執行時間和空間限制執行時間和空間限制執行時間和空間限制嗎嗎嗎嗎 (Does the recursive solution run in(Does the recursive solution run in acceptable timeacceptable time and and space limitsspace limits)?)?Note:19 遞迴演算法則的複雜度分析遞迴演算法則的複雜度分析u遞迴演算法的分析比iterative algorithm的分析要來得困難。

u分析步驟:n我們找出遞迴演算法的遞迴方程式遞迴方程式遞迴方程式遞迴方程式 T(nT(n)(recurrence)(recurrence equation,equation,或通稱為Time function,Complexity Time function,Complexity functionfunction亦可)來表達該演算法的執行次數n接著，解這個遞迴方程式來求出該演算法的時間複雜度時間複雜度時間複雜度時間複雜度20遞迴演算法的遞迴方程式遞迴演算法的遞迴方程式u以“Factorial”為例，透過對遞迴關係與終止條件的分析，我們可以得知Factorial遞迴演算法的遞迴方程式(時間函數)如下:T(n)=T(n-1)T(n-1)+1 u每執行一次遞迴呼叫後，接著可能每執行一次遞迴呼叫後，接著可能還需要之還需要之“遞迴呼叫的執行次數遞迴呼叫的。