[BEB_07] DAY 11 재귀

학습목표

재귀 함수에 대해 알고, 활용하기

 

재귀 함수란 내부적으로 자기 자신을 호출하는 함수이다.

반드시 탈출조건이 필요하고, 재귀 호출을 너무 많이 하게 되면 스택 메모리가 과부하

(스택 오버플로)가 발생할 수 있다는 단점이 있다.

그래도 재귀함수를 쓰는 이유는 가독성이 좋다.

개발은 여러사람이 함께 협업으로 이루어지는 것이라 가독성이 무척 중요하다.

 

 

재귀 함수는 트리구조이다.

트리 구조하면 배웠던 것 중에 DOM이 생각난다.

트리, DOM, JSON 구조에 재귀 함수를 활용해보자.

 

재귀적 사고연습을 위해 코드 작성 시 수도 코드로 base case와 recursive case로 나눠서 작성해보자.

재귀는 언제 사용하는 게 좋을까?

1. 주어진 문제를 비슷한 구조의 더 작은 문제로 나눌 수 있는 경우

2. 중첩된 반복문이 많거나 반복문의 중첩횟수를 예측하기 어려운 경우

 

재귀적으로 사고하기

1. 재귀 함수의 입력값과 출력값 정의하기

2. 문제를 쪼개고 경우의 수를 나누기

 - 주어진 문제를 어떻게 쪼갤 것인지 고민한다. 

   문제를 쪼갤 기준을 정하고, 정한 기준에 따라 문제를 더 큰 경우와 작은 경우로 구분할 수 있는지 확인한다.

  일반적인 경우, 입력값으로 이 기준을 정한다. 이때 중요한 관점은 입력값이나 문제의 순서와 크기이다.

  주어진 입력값 또는 문제상황을 크기로 구분할 수 있거나, 순서를 명확하게 정할 수 있다면 문제를 구분하는 데 도움이 된다.

3. 단순한 문제 해결하기

 - 문제를 여러 경우로 구분한 다음에는, 가장 해결하기 쉬운 문제부터 해결한다. 

  이를 재귀의 기초(base case)라고 부른다. 

  재귀의 기초는 나중에 재귀 함수를 구현할 때, 재귀의 탈출 조건(재귀 호출이 멈추는 조건)을 구성한다.

4. 복잡한 문제 해결하기

5. 코드 구현하기

 

재귀는 반복할 구문을 함수 단위로 분리해, 특정 조건이 만족할 때까지 실행하는 패턴으로 볼 수 있다.

n! = n * (n-1)!

"n이 2가 될때까지 위 구문을 반복"

 

기본적으로 반복문이므로, 모든 재귀는 반복문으로 표현할 수도 있다.

// 재귀

function factorial (n) {

 if ( n === 0 ) {                          // base case : n이 0이면 재귀를 더 이상 진행하지 않는다.

    return 1 ;                              

}

 return n * factorial ( n - 1 );     // recursive case

}

 

// 반복

function factorial (n) {

 let result = 1 ;

 for (let i = n; i > 0 ; i--) {

   result = result * i ;

}

  return result ;

}

 

JSON

JSON 은 JavaScript Object Notation의 줄임말로, 데이터 교환을 위해 만들어진 객체 형태의 포맷이다.

 

기본규칙

	자바스크립트 객체	JSON
키	키는 따옴표 없이 쓸 수 있음	반드시 큰 따옴표를 붙여야 함
문자열 값	문자열 값은 어떠한 형태의 따옴표도 사용가능	반드시 큰따옴표를 감싸야 함

또한 JSON은 키와 값 사이, 그리고 키-값 쌍 사이에는 공백이 있어서는 안 된다.