[TIL] JS - 재귀

Today I Learned

재귀 (Recursion)

• 재귀란 함수가 스스로를 호출하는 것을 말한다.
• 재귀 함수는 base case와 recursive case 두 부분으로 나누어져 있다.
• 함수 호출시 해당 함수가 stack에 쌓이는데 재귀를 잘못 사용하면 stack overflow가 일어날 수도 있다.

재귀 함수를 사용하면 좋은 경우

• 반복문 중첩이 너무 많이 일어나거나 반복 횟수를 예측하기 어려운 경우, 반복문으로 표현할 수도 있지만 재귀를 적용하면 코드가 간결해지고 가독성이 높아진다.
• 반복문은 재귀에 비해 메모리 비용이 적고 재귀는 반복문에 비해 가독성이 좋다. 경우에 따라 적절하게 사용한다.

재귀를 사용하여 문제 풀기

1. 문제를 더 작은 문제로 쪼개지는지, 구분된 문제들을 푸는 방식이 순서/크기에 상관 없이 같은지 확인
2. 구분된 문제들 중 가장 간단한 문제부터 해결하기 (base case)
3. 남은 문제를 재귀적으로 해결하기 (recursive case)

// 재귀 함수 기본 구조
function recursion(input) {
  // base case
  if (더 이상의 recursion이 불가능한 경우) return 가장 간단한 문제의 답;
  // recursive case
  return 더 작아진 input으로 recrusion 함수를 재귀적으로 호출
}

재귀 사용 시 주의할 점

• 잘못된 base case 사용 또는 base case가 없는 경우
• 잘못된 return 또는 return이 없는 경우
• stack overflow
• 함수에 주어진 인자의 원본을 훼손하지 않도록 주의

예시

피보나치 : 피보나치 수열의 n번째 값 구하기

// 재귀로 구현
function fibonacci(n) {
  // base case :
  if (n === 0 || n === 1) return n;
  // recursive case :
  	// 피보나치 수열의 n번째 수는 n-1번째 수와 n-2번째 수의 합과 같다
  return fibonacci(n-1) + fibonacci(n-2);
}

// 반복문으로 구현
function fibonacci(n) {
  if (n === 0 || n === 1) return n;
  let cur = 1;
  let prev = 0;
  for (let i = 2; i <= n; i++) {
    let temp = prev;
    prev = cur;
    cur += temp;
  }
  return cur;
}

배열 평탄화 (Flatten Array) : 다차원 배열을 1차원 배열로 변환하여 리턴

function flattenArr(arr) {
  let result = [];
  
  // base case :
  if (arr.length === 0) return result;
  
  // recursive case :
  const first = arr[0];
  if (Array.isArray(first)) {
    result.push(...flattenArr(first));
  } else {
    result.push(first);
  }
  result.push(...flattenArr(arr.slice(1)));
    
  return result;
}
  
// OR : 재귀 + 반복문 
function flattenArr(arr) {
  let result = [];
  
  for (let el of arr) {
    if (Array.isArray(el)) {
      result.push(...flattenArr(el));
    } else {
      result.push(el);
    }
  }
  
  return result;
}

// OR : 반복문 대신 reduce 사용
function flattenArr(arr) {
  return arr.reduce((acc, cur) => {
    if (Array.isArray(cur)) {
      return acc.concat(flattenArr(cur))
    } else {
      return acc.concat(cur);
    }
  }, []);
}