[JS] 재귀 함수 1

✨ 재귀함수

• 재귀함수는 자기 자신을 호출하는 함수이다.
  • 자기 자신을 호출하는 것을 재귀 호출(Recursion call)이라고 한다.
• 함수 호출은 Call stack에 쌓이기 때문에 스택 자료구조와 유사하게 동작한다.
• 함수형 프로그래밍에선 루프 구현을 재귀로 구현하는 경우가 많다.
• 잘못 작성하면 무한 루프에 빠질 수 있다.

 

Javascript에서 재귀함수

• Call stack 제한이 있다.
  • 자바스크립트 엔진마다 제한 수는 다르다.
  • 크롬의 경우 약 1만개이다.
• 재귀함수 성능 개선을 위한 꼬리 재귀(Tail recursion)가 제공되지 않는다.
• 성능이 좋지 않다.

 

재귀로 구현해야 편한 알고리즘

• Union-Find
• DFS
• Backtracking
• 불편함을 무시한다면 더 빠른 성능으로 작성할 수 있지만 코딩 테스트는 빨리 푸는 것이 중요하기에 추천하지는 않는다.

 

---

✨ 재귀함수 예시 코드

1. 탈출 조건 작성하기

재귀 함수를 작성할 때는 반드시 탈출할 수 있는 조건을 작성해야 한다.

function recursion(a) {
  return recursion(a + 1);
}

이렇게 탈출 코드가 없으면 무한 루프에 빠진다.

자바스크립트에선 call 제한수가 있기때문에 결국 함수가 런타임 에러가 발생하게 된다.

 

따라서 if문 등의 조건문을 통해 탈출할 수 있는 코드를 작성해야한다.

function recursion(a) {
  if (a > 10) {
    return a;
  }
  return recursion(a + 1);
}

console.log(recursion(5)); // 11

 

2. 피보나치 수열

앞 두 항의 합이 뒤 항의 값이 되는 수열

// 1 1 2 3 5 8 13 ...
function fivonacci(x) {
  if (x <= 2) {
    return 1;
  }
  return fibonacci(x - 1) + fibonacci(x - 2);
}

console.log(fivonacci(7)); // 13

왼쪽 루트만 보자면 이런식으로 함수 호출이 진행된다.

3에서 내려온 fibonacci(2)와 fibonacci(1)은 탈출 루트를 통해 각각 1을 반환한다.

 

 

3. 변수 없는 합병 정렬 구현

분할 합병을 통한 정렬 구현

// 결합
const merge = (a, b) => {
  if (a.length === 0) {
    return b;
  } else if (b.length === 0) {
    return a;
  } else if (a[0] < b[0]) {
    return [a[0], ...merge(a.slice(1), b)];
  } else {
    return [b[0], ...merge(a, b.slice(1))];
  }
}

// 분해
const mergesort = (arr) => {
  if (arr.length < 2) {
    return arr;
  } else {
    const mid = Math.floor(arr.length / 2);
    const argu1 = mergesort(arr.slice(0, mid));
    const argu2 = mergesort(arr.slice(mid));
    return merge(argu1, argu2);
  }
}

const arr = [21, 10, 12, 20, 25, 13, 15, 22];
console.log(mergesort(arr));
// [10, 12, 13, 15, 20, 21, 22, 25]