재귀함수

재귀 함수란?

재귀적으로 호출되는 함수가 반환 값을 이용해 문제를 분할하고, 작은 문제를 해결하여 최종적으로 전체 문제를 해결하는 방식입니다.

 

예시) recursion() 함수가 자기 자신을 호출하여 문제를 해결하는 재귀함수

function recursion () {
  console.log("This is")
  console.log("recursion!")
  recursion()
}

---

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

재귀함수는 다음과 같은 경우에 사용하는 것이 적합합니다.
(예를 들어, 피보나치 수열, 이진 탐색, 하노이 탑, 트리 순회 등은 재귀함수를 이용해 간단하고 명확하게 구현할 수 있습니다.)

1. 문제를 작은 부분으로 쪼개기 쉬운 경우
   
   • 문제를 작은 부분으로 쪼개기 쉽다면, 재귀 함수를 이용하여 작은 부분에서 해결하고 이를 결합하여 전체 문제를 해결할 수 있습니다. 이를 통해 코드의 가독성과 유지보수성을 높일 수 있습니다.
2. 반복문 대신 사용해야 하는 경우
   
   • 일반적으로 반복문으로도 문제를 해결할 수 있지만, 반복문을 사용하면 코드가 복잡해지거나 가독성이 떨어지는 경우가 있습니다. 이런 경우에는 재귀 함수를 사용하면 더 간결하고 직관적인 코드를 작성할 수 있습니다.
3. 데이터 구조가 재귀적인 구조를 가지고 있는 경우
   
   • 트리, 그래프 등과 같이 재귀적인 구조를 가지는 데이터 구조는 재귀 함수를 사용하여 문제를 해결하는 것이 적합합니다. 이를 통해 코드를 간결하게 작성하고, 문제 해결에 대한 직관성을 높일 수 있습니다.

재귀함수는 문제 해결 방법을 직관적으로 표현할 수 있으며, 코드를 간결하게 작성할 수 있는 장점이 있습니다. 하지만 재귀 호출이 너무 깊어지는 경우, 스택 오버플로우와 같은 문제가 발생할 수 있으므로, 사용할 때는 주의가 필요합니다. 기저 조건을 설정하는 것이 중요합니다.

예시) 중첩된 반복문이 많거나 반복문의 중첩 횟수(number of loops)를 예측하기 어려운 경우

for (let i = 0; i < n; i++) {
    for (let j = 0; j < n; j++) {
        for (let k = 0; k < n; k++) {
            for (let l = 0; l < n; l++) {
                for (let m = 0; m < n; m++) {
                    for (let n = 0; n < n; n++) {
                        for (let o = 0; o < n; o++) {
                            for (let p = 0; p < n; p++) {
                                // do something
                                someFunc(i, j, k, l, m, n, o, p);
                           }
                        }
                    }
                }
            }
        }
    }
 }

모든 재귀 함수는 반복문(while 문 또는 for 문)으로 표현할 수 있습니다. 그러나 재귀를 적용할 수 있는 대부분의 경우에는, 재귀를 적용한 코드가 더욱 간결하고 이해하기 쉽습니다.

예시) 1부터 n까지의 합을 구하는 반복문과 재귀 함수를 비교

반복문을 사용한 예시 코드:

function sum(n) {
  let result = 0;
  for (let i = 1; i <= n; i++) {
    result += i;
  }
  return result;
}

// 예시
console.log(sum(10)); // 출력 결과: 55

재귀 함수를 사용한 예시 코드:

function sum(n) {
  if (n === 1) { // 기저 조건: n이 1인 경우
    return 1;
  } else { // 문제 분할 및 재귀 호출
    return n + sum(n-1);
  }
}

// 예시
console.log(sum(10)); // 출력 결과: 55

위 두 코드는 같은 결과를 반환하지만, 재귀 함수를 사용한 코드는 반복문을 사용한 코드보다 코드가 더 간결해 보입니다. 하지만 반복문을 사용한 코드는 재귀 함수를 사용한 코드보다 코드의 실행 시간이 더 빠릅니다.

따라서 반복문과 재귀 함수를 선택할 때는 상황에 따라 적절한 것을 선택하는 것이 중요합니다. 일반적으로 단순한 반복문이나 재귀 함수의 경우에는 실행 속도의 차이가 크지 않지만, 반복 횟수가 많은 경우에는 재귀 함수를 사용하는 것이 실행 속도가 느려질 수 있습니다.

---

대표적인 재귀 함수 작성 방법

• 기저 조건(base case) 설정: 재귀적 호출을 끝내기 위한 조건을 설정합니다. 일반적으로 문제의 해결이 더 이상 필요하지 않을 때 함수를 종료하도록 합니다.
• 문제 분할: 문제를 작은 부분으로 나누고, 재귀적으로 호출할 수 있는 형태로 만듭니다.
• 재귀 호출: 함수 내에서 자기 자신을 호출합니다.

예시) 팩토리얼 계산 함수

function factorial(n) {
  if (n === 0) { // 기저 조건: n이 0인 경우
    return 1;
  } else { // 문제 분할 및 재귀 호출
    return n * factorial(n-1);
  }
}

// 예시
console.log(factorial(5)); // 출력 결과: 120

위의 예시에서 factorial 함수는 n의 팩토리얼을 반환합니다. 함수 내에서 자기 자신을 호출하고 있으며, n이 0일 때는 재귀 호출 없이 1을 반환하고 있습니다. 이처럼 자바스크립트에서도 재귀함수를 작성할 때는 기저 조건을 반드시 설정해야 합니다.

---

재귀적으로 생각하기

재귀적으로 생각하는 방법은, 큰 문제를 작은 문제로 분할하고 작은 문제를 해결하는 과정을 반복하여 전체 문제를 해결하는 것입니다. 이를 위해서는 큰 문제를 작은 문제로 나누는 능력과, 작은 문제를 해결하고 이를 결합하여 전체 문제를 해결하는 능력이 필요합니다.

재귀적으로 생각하는 방법을 연습하기 위해서는, 다음과 같은 절차를 따를 수 있습니다.

1. 문제를 큰 부분과 작은 부분으로 분할합니다.
2. 작은 부분을 해결할 수 있는 함수를 만듭니다.
3. 함수를 호출하여 작은 부분을 해결합니다.
4. 작은 부분의 해답을 결합하여 큰 부분을 해결합니다.
5. 2~4번 과정을 반복하여 전체 문제를 해결합니다.

예를 들어, 1부터 n까지의 합을 구하는 문제를 생각해보겠습니다. 이 문제를 재귀적으로 해결하기 위해서는, 다음과 같은 방법을 사용할 수 있습니다.

1. 문제를 큰 부분과 작은 부분으로 분할합니다. n의 합을 구하는 문제를 n-1의 합과 n을 더하는 문제로 나눕니다.
2. 작은 부분을 해결할 수 있는 함수를 만듭니다. n의 합을 구하는 함수 sum(n)을 작성합니다.
3. 함수를 호출하여 작은 부분을 해결합니다. sum(n-1)을 호출하여 n-1까지의 합을 구합니다.
4. 작은 부분의 해답을 결합하여 큰 부분을 해결합니다. sum(n-1)의 결과와 n을 더하여 n까지의 합을 구합니다.
5. 2~4번 과정을 반복하여 전체 문제를 해결합니다.

이렇게 재귀적으로 문제를 해결하는 방법은, 분할 정복 알고리즘과 같은 알고리즘 설계 기법에서도 널리 사용됩니다. 연습을 통해 재귀적으로 생각하는 능력을 기르면, 복잡한 문제를 단순한 방식으로 해결할 수 있게 됩니다.

예시코드) 1부터 n까지의 합을 구하는 재귀 함수

function sum(n) {
  if (n === 1) { // 기저 조건: n이 1인 경우
    return 1;
  } else { // 문제 분할 및 재귀 호출
    return n + sum(n-1);
  }
}

// 예시
console.log(sum(10)); // 출력 결과: 55

위의 예시에서 sum 함수는 1부터 n까지의 합을 반환합니다. 함수 내에서 자기 자신을 호출하고 있으며, n이 1일 때는 재귀 호출 없이 1을 반환하고 있습니다. 이처럼 자바스크립트에서도 재귀함수를 작성할 때는 기저 조건을 반드시 설정해야 합니다.