# 遞迴Recursive
###### tags: `演算法`

## recursive algorithm
1. 找出終止條件 Base Case
2. 訂出recursive step
3. recursive的參數如何改變

*recursive is a strategy for sloving a problem*
#### an easy example

def recursive(n):
    if n==0:
        return 0
    else:
        return recursive(n-1)

---
### N階層問題 Factorial
* base case：**n=0**
* recursive step：**n-1**
* 舉例 5! = 5* 4* 3* 2* 1 = 120

int factorial(int n){
    if(n==0){
        return 1;
    }else{
        return n*factorial(n-1);
    }
}

---
### 河內塔問題
* 問題描述：搬動盤子從A柱到C柱，一次只能搬動最上層的盤子，且小盤子不能在大盤子下
* base case：盤子只剩一個，直接搬動
* recursive step：
1. move n-1 disks to 2rd peg
2. move bottom disk to 3rd peg
3. move n-1 disks from 2rd peg to 3rd peg
* 最少步數為 2^n-1 步

public static void main (String[] args){
    hanoi(3,'A','B','C');
}
public static void hanoi(int disk, char start, char finish, char temp){
    if(disk==1){
        System.out.println("move disk"+disk+" from peg"+start+" to peg"+finish);
        //搬動最底層disk
        return;
    }else{
        hanoi(disk-1, start, temp, finish);
        //把n-1個disk搬動到暫時的柱子，接著會做base case
        System.out.println("move disk"+disk+" from peg"+start+" to peg"+finish);
        hanoi(disk-1, temp, finish, start); 
        //再把n-1個disk搬回C柱，也把bottom搬回C柱
    }
}
    

程式結果：

move 1 from A to C
move 2 from A to B
move 1 from C to B
move 3 from A to C
move 1 from B to A
move 2 from B to C
move 1 from A to C

---
### 費式數列 Fibonacci Numbers
* 問題描述：**F(n) = F(n-1) + F(n-2)**
* base case：**n=0 , n=1**
* recursive case： **n-1 , n-2**

int fibonacci(int n){
    if(n==0){
        return 0;
    }else if(n==1){
        return 1;
    }else{
        return f(n-1)+f(n-2);
    }
}

---
### 最大公因數 GCD
* 問題描述：利用輾轉相除法來找
* base case：**a or b = 0**
* recursive case：大數除小數取餘數

int GCD(int a, int b){
    if(b==0){
        return a;
    }else if(a==0){
        return b;
    }else{
        if(a>b){
            return GCD(a%b,b);
        }else if(b>a){
            return GCD(a,b%a);
        }else{
            return a;  //a、b相等
        }
    }
}

---
### 數學組合公式 Pascal’s triangle
* 問題描述：**C(n取r) = C(n-1取r) + C(n-1取r-1)**
* base case： **n=n,C=1; r=0,C=1; r=1,C=n;**
* recursive case：照公式寫

int math(int n, int r){
    if(n==r){
        return 1;
    }else if(r==1){
        return n;
    }else if(n==0){
        return 1;
    }else{
        return math(n-1,r)+math(n-1,r-1);
    }
}

---
### 找質數
* 問題描述：找質數遞迴寫法
* base case：**n<=2**
* recurisve step：
1. n % i 來判斷
2. i * i > n 來判斷
3. **isPrime(n,i+1)**

bool isPrime(int x, int i=2){
    if(x<=2){
        if(x==2){return true;}
        else{return false;}
    }
    if(x%i==0){return false;}
    if(i*i>x){return true;}
    return isPrime(x,i+1);
}

---
### Binary Search
* 有left、right、mid三個索引值
* 需傳入 sorted array
* recursive step:
1. 比 mid 大，就往arr右邊找
2. 比 mid 小，就往arr左邊找
3. == mid, return mid

def binarySearch(arr, left, right, target):
    # check base situation
    if right >= left:
        mid = int((left+right)/2)
        if target > arr[mid]:
            left = mid + 1
            return binarySearch(arr, left, right, target)
        elif target == arr[mid]:
            return mid
        elif target < arr[mid]:
            right = mid - 1
            return binarySearch(arr, left, right ,target)
    else:
        return -1

#num = [10, 16, 22, 27, 31, 39, 46, 49, 52, 55, 61, 72, 84, 95]
#print(binarySearch(num, 0, len(num)-1, 95))