[Algorithm] RECURSION (재귀)

✍ 정의

일반적으로 재귀란 다음과 같은 사전적 의미를 가지고 있다.

어떠한 것을 정의할 때 자기 자신을 참조하는 것을 뜻 한다.

이러한 재귀는 프로그래밍에서는 주로 함수가 자기 자신을 참고하는 것을 뜻하며, 이러한 함수를 재귀 함수라고 칭한다.

보통 재귀함수는 프로그래밍에서 for, while, do...while문과 같은 반복문을 사용해서도 구현할 수 있는데 이러면 코드의 길이도 길어지고 가독성이 떨어진다는 단점이 있어 재귀함수의 특징을 살려 적용하는 것이 더 괜찮다.

✍ 재귀 함수의 특징

반복문과 비슷한 특징을 가지고 있는데 실행하는 문이 본인의 함수라는 것이 조금 다르다

• Continuation : 특정 조건을 만족할 경우, 다시 실행하는 부분으로, 자기 자신을 다시 실행한다.
• Termination : 특정 조건을 만족할 경우, 함수를 종료한다.

얼핏 위 특징을 보면 반복문과 큰 차이가 없는 것으로 보이기에 직접 코드 예제를 통해서 얼마나 달라지는지 비교해보자.

✍ 예제로 살펴보는 재귀 함수

📝 팩토리얼 함수

function solution(n) {
  let factorial = [1, 1];
  for (let i = 2; n > factorial[i - 1]; i++) 
      factorial[i] = factorial[i - 1] * i;
  return factorial[factorial.length - 1] === n ? factorial.length - 1 : factorial.length - 2;
}

function solution(n) {
    if (n == 0) {
        return 1;
    } else {
        return n * solution(n - 1);
    }
}

첫 번째 함수와 같이 가독성이 떨어지는 팩토리얼 함수가 재귀 함수의 특징을 살려서 다시 정의하면 다음과 같아 질 수 있다 .

이렇게 재귀적 표현을 사용하는 방식은 다양한데, 최근에는 MySQL에서도 재귀적 표현을 이용해서(WITH RECURSION) 표를 하나 생성한 적이 있다.

📝 재귀적 표현을 이용한 표 생성(MySQL)

WITH RECURSIVE cte (n) AS
(
  SELECT 1
  UNION ALL
  SELECT n + 1 FROM cte WHERE n < 5
)
SELECT * FROM cte;

아직 초보 개발자이다보니 재귀적 표현이 사용된 예제를 찾기는 쉽지 않지만, 자기 자신의 결과 값을 다시 참조하는 문제는 풀다보면 자주 등작하니 굳이 함수가 아니더라도 재귀적 표현은 알아두면 좋을 것 같다.

⇒ 한 가지 주의해야 할 점은, 재귀적 표현은 반복문과 유사하다 보니 잘못 사용하면 StackOverflow나 RecursionError결과를 나을 수 있다.