遞迴演算法

葉桔良

定義：演算法(函式)中有呼叫自己(Self Calling)的敘述

目的：重複執行一段程式
        (可以用迴圈也可以用遞迴來處理，因此迴圈必可改寫成遞迴，反之亦然)

特性：
    1.程式碼簡潔
    2.執行效率較迴圈慢
    3.將控制權轉移到呼叫的函式
    4.呼叫函式後要將變數值及狀態由Stack中Pop出來
    (維基百科：堆疊)

遞迴的種類：


遞迴的要素：
    1.遞迴關係式：找出問題共通的關係，以便反複呼叫自己
    2.終止條件：遞迴結束的條件

白話版的遞迴例子：

從前有座山，山裡有座廟，廟裡有個老和尚講故事，講的什麼呢？從前有座山，山裡有座廟，廟裡有個老和尚講故事，講的什麼呢？從前有座山，山裡有座廟，廟裡有個老和尚講故事，講的什麼呢？從前有座山，山裡有座廟...



累加程式範例

1. import java.util.Scanner;
   
2. public class JPD03 {
   
3.     static Scanner keyboard = new Scanner(System.in);
   
4.     public static void main(String args[]) {
   
5.         int n;
   
6.         while(true)
   
7.         {
   
8.                 System.out.print("Input n : ");
   
9.                 n=keyboard.nextInt();
   
10.                 System.out.println(n+"的累加="+add(n));
    
11.         }
    
12.     }
    
13.    
    
14.     static int add(int n)
    
15.     {
    
16.             if(n==1)   //邊界條件
    
17.             {
    
18.                     return 1;
    
19.             }else
    
20.             {
    
21.                     return n+add(n-1);
    
22.             }
    
23.     }
    
24. }
    
25. // 10 + add(9)
    
26. // 10 + 9 + add(8)
    
27. // . . .
    
28. // 6 * 5 * 4 * 3 * 2 * 1  
    
29. 
    
30. 
    
31. 
    
32. 
    
33. 
    
34. 
    
35. /*     遞迴程式設計
    
36. 
    
37.        cal(5)
    
38.        =5+cal(4)
    
39.        =5+4+cal(3)
    
40.        =5+4+3+cal(2)
    
41.        =5+4+3+2+cal(1)
    
42.        =5+4+3+2+1
    
43. */

複製代碼