[資料結構(Data Structure, DS)] 基礎遞迴

遞迴演算法

• 重複執行
  • 重複執行一段程式，可用
    • 迴圈(Iteration)
    • 遞迴(Recursion)
  • 迴圈必可改寫成遞迴，反之亦然
• 遞迴演算法
  • 演算法(函式)中有呼叫自己(Self Calling)的敘述
  • 特性：
    • 程式碼簡潔
    • 執行效率較迴圈慢
      • 呼叫函式前要將目前的變數值及狀態Push到Stack中
        • 參數值(Parameter)
        • 區域/暫存變數值(Local Variable)
        • 返回位址(Return Address)
    • 將控制權轉移到呼叫的函式
    • 呼叫函式後要將變數值及狀態由Stack中Pop出來
• 遞迴的種類

  直接遞迴(Direct Recursion)	間接遞迴(Indirect Recursion)	尾端遞迴(Tail Recursion)
  函式直接呼叫自己	函式呼叫另一函式，再由另一函式呼叫自己	直接遞迴的特例， 函式在結束的前一行呼叫自己

• 遞迴的要素：
  • 遞迴關係式：找出問題共通的關係，以便反複呼叫自己
  • 終止條件：遞迴結束的條件
• 遞迴設計：
  • 決定基本情況(Base Case)：遞迴的終止條件
  • 決定一般情況(General Case)：即遞迴關係式
  • 演算法設計

    function 函式名稱(參數)
    {
        if( Base Case)
            return (結果);    //達到終止條件
        else
            General Case;    //執行遞迴呼叫
    }