[DataStructure] Recursion

Recursion Explanation

• Pros : Readability, DRY
• Cons : Large Stack

Recursion 언제 써야하나?

Every time you are using a tree or converting Something into a tree, consider recursion.

1. Divided into a number of subproblems that are smaller instances of the same problem
2. Each instance of the subproblem is identical in nature
3. The solutions of each subproblem can be combined to solve the problem at hand

Then, Divide and Conquer using Recursion

Debug with Chrome Devtools

아래 코드를 Chrome console에서 실행시켜본다.

let counter = 0;
function inception() {
  debugger;
  if (counter > 3) {
    return 'done'; // 1. Base case
  }
  counter++;
  return inception(); // 2. Recursive Case
}

inception()

1. Identify the base case
2. Identify the recursive case
3. Get closer and closer and retrun when needed. Usually you have 2 returns (1과 2에서 각각 return이 있으므로, 보통 2가지 return이 있다.)

이미지를 보면, 왼쪽아래 Call Stack이 쌓인다. 오른쪽아래 Scope에서 현재 Return Value를 볼 수 있다. debugger를 통해서 Recursion의 Call Stack에서의 Return Value를 확인할 수 있는 것이다.

Practice

• Factorial
• Fibonacci
• Reverse string

Terms

Tail Call Optimization