재귀와 스택

재귀

사전적 정의: 본래 있던 곳으로 다시 돌아옴
프로그래밍 정의
1. 문제 해결을 위해 함수 자신을 다시 호출
2. 어떤 프로시저(절차)가 자기 자신을 반복적 호출하여 문제를 풀어가는 알고리즘

재귀는 큰 목표 작업 하나를 동일하면서 간단한 작업 여러 개로 나눌 수 있을 때 유용한 프로그래밍 패턴이다. 목표 작업을 간단한 동작 하나와 목표 작업을 변형한 작업으로 단순화 시킬 때 사용.
문제 해결을 위해 함수에서 다른 함수를 호출 하는데, 그때 자기 자신을 호출하는 것을 재귀라고 함.

// pow 함수를 재귀 호출 방식으로 변경
// - 재귀 기반(base)
// - 재귀 단계(step)
// - 재귀 깊이(depth)
function pow(x, n) {
  if (n == 1) {
    return x;
  } else {
    return x * pow(x, n - 1);
  }
}
console.log(pow(2, 3));
// factorial 함수를 재귀 호출 방식으로 작성
// - 팩토리얼 = 그 수보다 작거나 같은 모든 양의 정수의 곱
// - 기호(!)를 사용하여 n!으로 표기
// - 예시) 4! = 4 * 3 * 2 * 1
function factorial(n) {
  if (n == 1) {
    return n;
  } else {
    return n * factorial(n - 1);
  }
}

실행 컨텍스트(execusion context)의 작동 흐름

• 함수 실행에 대한 세부 정보를 담고 있는 내부 데이터 구조
• 제어 흐름의 현재 위치, 변수의 현재 값, this 등 저장.
• 함수가 호출될 때 마다, 하나의 실행 컨텍스트 생성

  내부에 중첩된 함수를 포함한 경우
  현재 함수의 실행 일시 중지
  중지된 함수와 연관된 실행 컨텍스트는 '실행 컨테그스트 스텍' 자료 구조에 저장됨
  중첩 함수가 호출되어 실행 됨(호출 시 새로운 컨텍스트 생성)
  중첩 호출 실행이 종료되면 실행 컨텍스트 스텍에서 일시 중단된 함수 실행 컨텍스트 꺼냄(pop)
  다시 중단되었던 함수의 실행을 이어감.

반복문 기반 알고리즘 vs 재귀 호출 알고리즘

1. 재귀 호출 알고리즘은 재귀 깊이만큼 메모리가 필요
2. 반복문 기반 알고리즘은 메모리가 절약됨

요약
1. 메모리 최적화 관점에서는 반복문 기반 알고리즘에 비해 메모리 사용도가 높은 점이 약점
2. 작성하는 모든 곳에서 메모리 최적화가 필요한 것은 아니므로 가독성을 높이는 코드가 필요
3. 재귀는 코드를 짧게 만들고, 코드 이해도를 높이며 유지보수에도 이점이 있어 많이 사용됨

메모이제이션

메모이제이션(memoization)은 컴퓨터 프로그램이 동일한 계산을 반복해야 할 때, 이전에 계산한 값을 메모리에 저장함으로써 동일한 계산의 반복 수행을 제거하여 프로그램 실행 속도를 빠르게 하는 기술.
자바스크립트에서는 임의 캐시 공간을 만들고 그 안에 계산값을 저장한다.

const memoFibo = (n) => {
  if (n <= 0) return 0;
  if (n <= 2) return 1;
  if (memoFibo.cache[n]) {
    return memoFibo.cache[n];
  } else {
    return (memoFibo.cache[n] = memoFibo(n - 1) + memoFibo(n - 2));
  }
};
memoFibo.cache = {};
//memoFibo에게 cache 라는 임의의 객체 저장소를 만들어주고 그 안에다가 저장함.

//객체 속성 재귀 호출
function isObject() {}
function isArray(data) {
  return Array.isArray(data);
}

function print(data) {
  if (typeof data === 'object') {
    for (let keyValue of Object.entries(data)) {
      let key = keyValue[0];
      let value = keyValue[1];
      if (typeof value === 'object' || Array.isArray(value)) {
        print(value);
      } else {
        console.log(`key: ${key}, value:${value}`);
      }
    }
  }
  if (Array.isArray(data)) {
    data.forEach((value, index) => {
      if (typeof value === 'object' || Array.isArray(value)) {
        print(value);
      } else {
        console.log(`key: ${index}, value:${value}`);
      }
    });
  }
}