遞迴 Recursive 授課老師：蕭志明

遞迴（ Recursive ） 一個副程式或函數重複的呼叫自己本身，稱為遞迴(Recursive)。 利用遞迴解決問題，既經濟又方便。 可用遞回來解決的問題，那它也一定可轉成利用非遞迴的方式解決之。 撰寫遞迴時，千萬小心，一定要有一個結束點，否則後果嚴重。 遞迴在執行時，會藉助堆疊將呼叫本身函數的下一個敘述位址儲存起來，待執行完結束點後，再將堆疊的資料一一的彈出來處理。

遞迴設計步驟 發展從一個或多個較小實例的解中得到較大實例的解之方式。 決定分割為較小實例的終止條件。 決定終止條件時的解。

階乘 求n!，一般可能用的規則： 利用迴圈： 利用遞迴： n! = n * (n-1)!; ans = 1; for (i = 2; i <= n; i++) ans = ans * i; 利用遞迴： int fact(int n) { int x, y; if (n == 0) // boundary condition return(1); x = n-1; y = fact(x); return(n*y); } /* end fact */

遞迴呼叫流程圖 n=4 int fact(int n) { int x, y; if (n == 0) // boundary condition return(1); x = n-1; y = fact(x); return(n*y); } /* end fact */ n=4 n=2 n=1 n=0 fact(2) … y=fact(1) fact(0) … Return(1) fact(4) … y=fact(3) n=3 fact(3) … y=fact(2) fact(1) … y=fact(0) Fact(2)=2 Fact(0)=1 Fact(3)=6 Fact(1)=1 Fact(4)=24

遞迴呼叫流程圖 練習：fact(5)的呼叫過程，遞迴呼叫流程圖為何。 n=5 int fact(int n) { int x, y; if (n == 0) // boundary condition return(1); x = n-1; y = fact(x); return(n*y); } /* end fact */ n=5

遞迴推疊圖 (The recursive stack) 呼叫過程: f4 f3 f2 f1 f0

The stack at various times during execution during execution. y (i)printf(“%d”, fact(3)) The stack at various times during execution during execution. (An asterisk indicates an uninitialized value.)

費氏數列 費氏數列 (Fibonacci number)： 利用遞迴範例： int fib(int n) f(0) = 0;* f(1) = 1; f(2) = f(1) + f(0); f(3) = f(2) + f(1); ： f(n) = f(n-1) + f(n-2); 利用遞迴範例： int fib(int n) { int x, y; if (n <= 1) return(n); x = fib(n-1); y = fib(n-2); return(x+y); } /* end fib */

遞迴呼叫流程圖 fib(4) … x=fib(3) fib(3) … x=fib(2) y=fib(1) y=fib(2) n=4 fact(2) … x=fib(1) y=fact(0) fib(1) Return(1) n=2 n=1 fib(1)=1 fib(2)=1 fib(0) Return(0) n=0 fib(0)=0 n=3 fib(3) … x=fib(2) y=fib(1) fib(3)=2 n=1 fib(1) Return(1) n=4 fib(1)=1 fact(2) … x=fib(1) y=fact(0) fib(1) Return(1) n=2 n=1 fib(1)=1 fib(2)=1 fib(0) Return(0) n=0 fib(0)=0 int fib(int n) { int x, y; if (n <= 1) return(n); x = fib(n-1); y = fib(n-2); return(x+y); } /* end fib */ fib(4)=3

遞迴推疊圖 (The recursive stack) 呼叫過程: f1 f2 f3 f4 f0

遞迴推疊圖 練習：fib(5)的呼叫過程，請用樹狀結構來表示。 n=5 int fib(int n) { int x, y; if (n <= 1) return(n); x = fib(n-1); y = fib(n-2); return(x+y); } /* end fib */ n=5

遞迴推疊圖 f5 f1 f2 f3 f4 f0 呼叫過程:

何時不要使用遞迴？ 遞迴雖然可以使用少數幾行的敘述就可以解決一些複雜的問題，但有些問題會使用更多的執行時間。 以費氏數列為例： 遞迴之複雜度為O(2n)，而迴圈只要O(n)。 約需時2n/2

結論 以階乘為例：無論使用遞迴或迴圈，複雜度階為O(n)。 但遞迴需要較大的記憶體空間。 結論： 執行過程不像灌木，而是一直線的前進與後退，如：階乘，亦不適用遞迴。 以迴圈會使程式困難設計時，可考慮用遞迴。