재귀 함수를 사용한 문제 해결

문제

어떠한 수 N이 1이 될 때까지 다음의 두 과정 중 하나를 반복적으로 선택하여 수행하려고 한다. 단, 두 번째 연산은 N이 K로 나누어떨어질 때만 선택할 수 있다.

1. N에서 1을 뺀다
2. N을 K로 나눈다

N과 K가 주어질 때, N이 1이 될 때까지 몇 번의 과정을 수행해야하는지를 구하시오.

 

며칠 전까지의 나였다면

사실 문제 자체는 아주 간단하다. while로 n이 1이 될 때까지 반복문을 돌리면서 외부 변수 count를 하나 만들고, 반복문이 한 번 시행될 때마다 count++를 해주면 끝이다.

function solution(N, K) {
  let count = 0;

  while (N > 1) {
    if (N % K === 0) N /= K;
    else N -= 1;

    count++;
  }

  return count;
}

이 문제는 그리디 알고리즘을 사용하여 풀 수 있는 전형적인 문제라고 할 수 있겠다. 그런데 오늘의 나는 이 문제를 반복문을 사용해 풀지 않았다. 이유는 간단한데, 어제 두 시간동안 재귀 함수에 대해 공부했기 때문이다.

while이라는 키워드를 사용하면 내가 반복문을 사용했다는 것을 조금 더 직관적으로 드러낼 수 있고, 이는 코드 가독성 부분에서도 어느정도 이점을 가져갈 수 있는 부분이라 생각한다. 그렇지만 코드를 읽는 사람이 재귀적 호출에 익숙하다면 재귀 함수를 사용해도 큰 문제는 없지 않을까 생각했다.

 

재귀 함수를 사용한 풀이

재귀 함수를 공부하면서 나는 크게 두 가지 부분에서 재귀적 문제 해결법에 대한 매력을 느꼈다. 첫번째는 커다란 문제를 더 작은 부분으로 반복하여 나누어서 생각하는 방식 그 자체가 멋있다. 두번째는 반복문을 사용할 때에 비해서 훨씬 더 적은 코드만으로도 문제를 해결할 수 있다는 것이다.

function solution(n, k) {
  if (n == 1) return 0;
  else if (n % k === 0) return solution(n / k, k) + 1;
  else return solution(n - 1, k) + 1;
}

반복문을 사용했을 때는 count 변수도 필요하고 12줄 길이로 함수가 만들어졌다. 그에 비해 재귀 함수를 사용하니 딱 5줄만 썼는데 문제가 뚝딱하고 해결되었다.

 

문제가 있다면 이제 막 재귀 함수를 배운 탓에 아직 숙련도가 높지 않다는 점 정도일까? 만약 문제가 조금 더 복잡했더라면 재귀적 문제 해결법을 시도할 엄두조차 못 내지 않았을까 싶기도 하다. 하지만 재귀 함수는 숙련도를 높여보고 싶을 만큼 충분히 매력적이다. 반복문으로 풀었던 문제들을 재귀 함수로 다시 풀어보려 한다.