[MasterThe Coding Interview]Algorithms:Recursion

發表於 分類於 閱讀次數：

本篇為MasterThe Coding Interview教學影片筆記文

Data Structures + Algorithms = Programs
Class{} + function() = Programs

Recursion的意思是一直提及自己，透過這個方式可以traversal tree、object和DOM。如果寫下一個沒有停止條件的recursion的話，會導致stack overflow，可以透過以下的程式碼在chrome查看stack overflow：

1
2
3
4
5
function loop(){
	//當瀏覽器看到debugger時會轉換成debug模式
	debugger;
	loop()
}

寫下recursive function的三個方法：

  1. Identify the base case
  2. Identify the recursive case
  3. Get closer and closer and return when needed.Usually tou have 2 returns
1
2
3
4
5
6
7
8
9
10
11
12
let counter = 0;
function inception(){
	console.log(counter)
	//base case
	if(counter > 3){
		return 'done!'
	}
	counter++;
	//recursive case
	return inception();
}
inception()

Exercise：Factorial

1
2
3
4
5
6
7
8
9
10
11
12
13
14
function findFactorialRecursive(number){
	if(number == 1){
		return 1;
	}
	return number * findFactorialRecursive(number - 1)
}

function findFactorialIterative(number){
	let answer = 1;
	for(let i = 2 ; i <= number ; i++){
		answer *= i
	}
	return answer
}

Exercise：Fibonacci

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
function fibonacciIterative(n){ //O(n)
	let arr = [0 , 1]
	if(n < 2){
		return arr[n];
	}
	for(let i = 2 ; i < n ; i++){
		let temp = arr[0] + arr[1];
		arr[0] = arr[1];
		arr[1] = temp;
	}
	return arr[0] + arr[1]; 
}

fibonacciIterative(3)

function fibonacciRecursive(n){ //O(2^n)
	if(n < 2){
		return n;
	}
	return fibonacciRecursive(n - 1) + fibonacciRecursive(n - 2)
}

fibonacciRecursive(3)

Recursive VS Iterative

優點 缺點
DRY Large Stack
Readability

以下是幾點要使用recursion的時機：

  1. 當使用到樹的結構來解決問題時，要考慮到recursion的解法。
  2. 當問題可分割並建立在相同的解法上時。
  3. 當需要計算一些總和且計算的方式都相同時。
  4. 當每個小問題可以結合來解決一個大問題的時候。

2,3,4點可以總結成Divide and Conquer的問題能利用Recursion解決。

所有可以利用recursion實作的例子都可以用loop解決。Ex：Merge Sort, Quick Sort, Tree Traversal, Graph Traversal。

Exercise：Reverse String

1
2
3
4
5
6
7
8
function reverseString(str) {
	if(str.length == 1){
		return str;
	}
	return str[str.length - 1] + reverseString(str.slice(0 , -1))
}

reverseString('yoyo mastery')

補充：Tail call optimization