###### tags: `學習記錄` `C#`
# 遞迴 Recursive
在同一個方法中，自己呼叫自己，用來處理重複的動作

**以階乘 n! 為例**
fn(1) = 1
fn(2) = 2 * 1
fn(3) = 3 * 2 * 1
fn(4) = 4 * 3 * 2 * 1

:arrow_down: :arrow_down: :arrow_down:

fn(1) = 1
fn(2) = 2 * fn(1)
fn(3) = 3 * fn(2)
fn(4) = 4 * fn(3)

**程式碼**

public int Factorial(int number){
    if(number == 1) {
        return 1;
    }
    else {
        return number * Factorial(number - 1);
    }
}

:::warning
需要確定 初始點 / 停止點，否則會離不開這個方法變成 Stack Overflow
:::

**以遍歷(Traverse)二元樹為例**
如需輸出 [1, 2, 3]
遍歷順序為：Value → Left → Right

public IList<int> PreorderTraversal(TreeNode root) {
    List<int> output = new List<int>();
    if(root != null) {
        // 先取得 value
        output.Add(root.val);
        // 再往 left 找數字，透過呼叫方法本身取得 value
        output.AddRange(PreorderTraversal(root.left));
        // 再往 right 找數字，透過呼叫方法本身取得 value        
        output.AddRange(PreorderTraversal(root.right));
    }        
    return output;
}

## 以 LeetCode 938. Range Sum of BST 為例

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */

public class Solution {
    public int RangeSumBST(TreeNode root, int low, int high) {
        int result = 0;
        if(root != null){
            if(root.val >= low && root.val <= high){
                result += root.val;
            }            
            result += RangeSumBST(root.left, low, high);
            result += RangeSumBST(root.right, low, high);
        }
        return result;
    }
}