返回列表 發帖

遞迴演算法

本帖最後由 葉桔良 於 2022-4-9 14:34 編輯

定義:演算法(函式)中有呼叫自己(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.        cal(5)
  31.        =5+cal(4)
  32.        =5+4+cal(3)
  33.        =5+4+3+cal(2)
  34.        =5+4+3+2+cal(1)
  35.        =5+4+3+2+1
  36. */
複製代碼

返回列表