大神的世界

若一個function自己呼叫自己，則我們稱這個function為recursive function

其中，recursive可以分為兩種

1. Direct recursion:  F1 -> F1 -> F1 -> ..... -> F1

2. Indirect recursion: F1 -> F2 -> F3 -> F1 -> F2 -> ... -> F3

在 recursive algorithm 中最最重要的是 boundary condition 否則會無限遞迴

例如說：

fact(n):

在 n = 0 時， 即 fact(0)， 函數 return 1

此時，這個 function 的 boundary condition 就是在 n = 0 時

流程:

fact(2)

2！ -> 2*1! -> 2*1*0! -> 2*1*1 -> 2*1 -> 2

multi(a, b):

a x b 可以看成 b 個 a 相加， 所以當 b 不等於 0 時， multi(a, b) 回傳 multi(a, b-1) + a

而當 b = 1 時， 只需回傳 a 即可

所以，multi(a, b)的 boundary condition 為 b = 1 時

流程：

multi(3, 4)

3*4 -> 3*3 + 3 -> 3*2 + 3 + 3 -> 3*1 + 3 +3 + 3 -> 3 + 3 + 3 + 3 -> 6 + 3 + 3 -> 9 + 3 -> 12

sum(n):   (Lec02)

sigma 1 to n = sigma 1 to n-1  + n

boundary condition 為 n = 1 時， 即 sum(1) = 1

流程：

sum(4)

sum(4) -> sum(3) + 4 -> sum(2) + 3 + 4 -> sum(1) + 2 + 3 + 4 -> 1 + 2 + 3 + 4 -> 3 + 3 + 4 -> 6 + 4 -> 10

binarySearch(arr[], target, left, right)

binarySearch 回傳值可分為3種情形

1. target > arr[middle]        return bin...(arr, target, middle+1, right)

2. target = arr[middle]        return arr[middle]     //found!!

3.  target < arr[middle]       return bin...(arr, target, left, middle-1)

boundary condition: 當 left > right 時 return 0   // not found QQ