JS_재귀 함수

재귀 함수

어떤 문제를 해결할 때, 구조는 동일하지만 더 작은 경우를 해결함으로써 그 문제를 해결하는 방법을 재귀(recursion)라고 한다.

재귀 함수란 함수 스스로를 호출하는 것

function foo(){
  foo();
}  

재귀 함수를 사용하기 적합한 경우

1. 주어진 문제가 (구조는 비슷하고) 더 작은 문제로 나누어질 수 있는 경우
2. 중첩된 루프가 많거나 중첩의 정도(number of loops)를 미리 알 수 없는 경우

재귀 함수의 일반적인 형태

function recursive(input1, input2, ...) {
  // 재귀의 기초 (base case)
  if (문제를 더 이상 쪼갤 수 없을 경우) {
    return 단순한 문제의 해답;
  }
  // recursive Case
  // 그렇지 않은 경우
  return 더 작은 문제로 새롭게 정의된 문제
  // 예1. someValue + recursive(input1Changed, input2Changed, ...)
  // 예2. someValue * recursive(input1Changed, input2Changed, ...)
}

재귀와 반복문

재귀는 기본적으로 반복문이므로, 모든 재귀는 반복문으로 표현 가능

// 재귀
function factiorial(n) {
  if (n === 0) {
    return 1;
  }  
  return n * factiorial(n - 1);
}  
  
 // 반복문
function factiorial(n) {
  let result = 1;
  for (let i = n; i > 0; i--) {
    result = result * i;
  }
  return result;
}  

재귀의 탈출 조건

재귀는 무한 반복을 방지하기 위해 반드시 탈출 조건이 있어야 함

function factorial(n) {
  // Base Case
  // n이 0이면 재귀를 더 이상 진행하지 않음
  if (n === 0) {
    return 1;
  }
  
  // Recursive Case
  return n * factorial(n - 1);
}  

재귀의 장점과 단점

• 장점 : 알고리즘이 재귀로 표현하기에 자연스러울 경우, 프로그램의 가독성이 좋음

• 단점 : 값이 리턴되기 전까지 호출마다 call stack을 새로 생성하므로, 메모리를 많이 사용함

재귀의 사용 예시

• case 1 : fibonacci 수열

• case 2 : tree 구조 탐색 - JSON, DOM Tree

JSON(JavaScript Object Notation)

데이터 교환을 위해 만들어진 포맷

JSON 예시

const message = {
  sender: "김코딩",
  receiver: "나해커",
  message: "해커야 알고리즘 풀기 대결할래?",
  createdAt: "2021-08-02 19:08:02"
}

JSON 객체를 문자열로 변환하는 방법

let transferableMessage = JSON.stringify(message);
console.log(transferableMessage);
// `{"sender":"김코딩","receiver":"나해커","message":"해커야 알고리즘 풀기 대결할래?","createdAt":"2021-08-02 19:08:02"}`

JSON.stringify()함수를 사용하여 직렬화(serialize)함

문자열을 JSON 객체로 변환하는 방법

let packet = `{"sender":"김코딩","receiver":"나해커","message":"해커야 알고리즘 풀기 대결할래?","createdAt":"2021-08-02 19:08:02"}`;

let obj = JSON.parse(packet)
console.log(obj)
/*
{
  sender: "김코딩",
  receiver: "나해커",
  message: "해커야 알고리즘 풀기 대결할래?",
  createdAt: "2021-08-02 19:08:02"
}
*/

JSON.stringify()와 반대의 일을 하는 JSON.parse() 함수를 사용하여 역직렬화(deserialize)함

JSON 규칙 ( 객체와의 차이 )

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

JSON은 키와 값 사이, 그리고 키-값 쌍 사이에는 공백이 있어서는 안 됨