5. Recursion.md

Recursion

Recursion 을 작은조각으로 쪼개고 문제 하나를 풀고 , 또 다시 작은 조각으로 나누고 문제 하나를 푸는 방식으로 이해하면 된다.

Objectives

• Recursion 의 정의와 어떻게 활용할 수 있는지 알아보자

• 재귀 함수에 가장 중요한 두가지 요소를 이해하자

• 콜 스택을 시각화 해서 디버깅과 재귀함수를 더 잘 이해하자

• helper method recursion 과 순수한 재귀를 사용해서 다양한 문제를 해결해보자

What is recursion?

A process (a function in our case) that calls itslef

왜 Recursion 을 알아햐 하는가!

모든곳에 사용한다!

• JSON.parse / JSON.stringfy 함수에서 재귀를 사용한다.
• document.getElementById and DOM 순회 algorithms
• Object 순회
• 이후에 복잡한 자료구조에서 재귀를 사용할 것이다.
• 가끔은 깔끔하게 하기 위해 반복문 대신에 사용할 수 도 있다.

Call Stack

자 이제 함수부터 이야기 해보자~

• 대두분의 프로그래밍 언어에는 함수 실행될 때 자료구조를 만드는 콜스택이 있다.
• call stack 은 스택 자료구조 이다.
• 함수를 불러올 때 마다 함수를 맨 위에 위치시킨다.
• 자바스크립트에서 return이나 함수가 끝날때 컴파일러는 맨 위에 것을 제거한다.

Why do I care?

• 함수가 콜스택에 올라가고 완료되면 제거된다.
• 재귀 함수를 작성하면 계속해서 새로운 함수를 콜스택에 올린다.

---

How recursive functions work

Invoke the same function with a different input until you reach you base case!

Base Case

The condition when the recursion ends.

Two essential parts of a recursive function!

• Base Case
• Different Input

1. Recursive Function

function countDown(num) {
	if(num <= 0) {
        console.log("All done!");
        return;
    }
    console.log(num);
    num--;
    countDown(num);
}

2.

function sumRange (num) {
    if(num ===1) return 1;
    return num + sumRange(num-1)
}

3. Factorial Function

// 반복문
function factorial(num) {
    let total = 1;
    for(let i = num; i > 0; i--) {
        total *= i
    }
    return total;
}

// 재귀
function factorial1(num) {
    if(num ===1) return 1
    return num * factorial(num-1)
}

Where things go wrong

• No base case (끝나는 지점이 없을 때)

• return 을 깜박하거나 잘못된 것을 return 할 때

• Stack Overflow

  function factorial (num) {
      if (num === 1) return 1;
      return num * factorial(num); // return wrong thing
  }

  function factorial (num) {
  	if (num === 1) console.log(1); //no basic case
      return num * factorial(num-1);
  }

Helper Method Recursion

• Example Let's try to collect all of the odd values in an array!

  function collectOddValues(arr) {
      
      let result = []
      
      function helper(helperInput) {
          // basic case
  		if(helperInput.length === 0) {
  			return
          }
          if(helperInput[0] % 2 !== 0){
  			result.push(helperInput[0])
          }
          
          helper(helperInput.slice(1))
      }
      helper(arr)
      
      return result;
  }

Pure Recursion

function collectOddValues(arr) {
    let newArr = [];
    
    if(arr.length === 0 ){
		return newArr;
    }
    
    if(arr[0] % 2 !== 0){
        newArr.push(arr[0]);
    }
    
    newArr = newArr.concat(collectOddValues(arr.slice(1)));
    return newArr;
}

Tips

• slice, the spread operator , concat 메소드는 원래 배열을 바꾸지 않는다.
• string은 변경 할 수 없기 때문에 slice, substr, substring 메소드를 사용하자
• 객체를 복사하기 위해 Objec.assign, the spread operator를 사용하자
• 배열을 만질 때는 return에 concat 가 자주 나온다