Ruby에서 재귀와 메모이제이션 활용하는 방법: 팩토리얼부터 피보나치까지

Ruby의 재귀(Recursion)란 무엇일까요?

재귀 함수란 종료 조건, 즉 기저 사례(base case)에 도달할 때까지 스스로를 계속 호출하는 함수를 말합니다. 함수가 호출될 때마다 기저 사례에 한 걸음씩 다가가며 남은 작업의 양을 점점 줄여 나갑니다.

기저 사례에 도달하면 재귀 호출이 멈추고, 함수들이 차례대로 결과를 반환하기 시작합니다.

Ruby로 구현하는 재귀: 팩토리얼 예제

재귀를 배울 때 가장 고전적인 예제는 팩토리얼(factorial) 계산입니다.

팩토리얼을 구하려면 1부터 목표 숫자까지의 모든 수를 곱해야 합니다. 예를 들어 5의 팩토리얼은 1 * 2 * 3 * 4 * 5 = 120입니다.

반복문과 재귀 두 가지 방식으로 모두 구현해 보겠습니다.

예제:

def iterative_factorial(n)
  (1..n).inject(:*)
end

def recursive_factorial(n)
  # 기저 사례(base case)
  return 1 if n <= 1

  # 재귀 호출
  n * recursive_factorial(n-1)
end

위 예제는 같은 팩토리얼 값을 반복(iteration) 방식과 재귀(recursion) 방식으로 각각 계산합니다.

재귀 버전에서는 다루는 숫자를 하나씩 줄여가며(n-1) 진행 상황을 만들어 갑니다. n이 1 이하가 되면 더 이상의 재귀 호출이 일어나지 않으며, 값은 다음과 같은 순서로 반환됩니다.

return 1      # recursive_factorial(1)
return 2 * 1  # recursive_factorial(2)
return 3 * 2  # recursive_factorial(3)
return 4 * 6  # recursive_factorial(4)
return 5 * 24 # recursive_factorial(5)

Ruby 개발자는 대부분의 경우 반복문 방식을 선택하곤 하는데, 물론 잘된 선택입니다. 그럼에도 재귀가 어떻게 동작하는지 이해해 두면 문제 해결의 폭이 넓어집니다.

이번에는 또 다른 고전적인 예제인 피보나치 수열을 살펴보겠습니다.

피보나치 수열(Fibonacci Sequence)

레오나르도 피보나치는 이상적인 조건에서 토끼 개체수의 증가를 모델링하는 방법을 연구하던 중 이 수열을 발견했습니다.

피보나치 수열은 현재 항 바로 앞에 있는 두 숫자를 더해 계산합니다.

예시:

1, 1, 2, 3, 5, 8, 13, 21

Ruby에서는 다음과 같은 재귀 함수로 구현할 수 있습니다.

def fib(n)
  return n if n < 2

  fib(n-1) + fib(n-2)
end

이 함수와 범위(range)를 조합하면 처음 20개의 피보나치 수를 손쉽게 구할 수 있습니다.

(1..20).each { |n| puts fib(n) }

그런데 여기에 심각한 문제가 있습니다:

이 함수는 불필요한 중복 작업을 아주 많이 수행합니다. 다음 이미지를 보면 문제가 무엇인지 한눈에 파악할 수 있습니다.

이미지에서 볼 수 있듯이 fib(3)은 무려 다섯 번이나 반복해서 계산됩니다. 더 긴 피보나치 수열을 계산하려고 하면 함수 실행 속도가 기하급수적으로 느려집니다.

해결책은 바로 메모이제이션(memoization)입니다.

메모이제이션: 이미 한 작업을 재사용하기

이전 단계에서 이미 해 둔 작업을 그대로 재사용할 수 있다면 얼마나 좋을까요?

바로 메모이제이션을 사용하면 가능합니다.

비용이 많이 드는 계산 결과를 저장하기 위해 캐시(cache)를 활용합니다. 이 경우에는 배열 하나면 충분합니다.

예제:

@cache = [0,1]

def fib(n)
  return @cache[n] if @cache[n]

  @cache[n] = fib(n-1) + fib(n-2)
end

동작 방식은 간단합니다. 먼저 결과가 캐시에 이미 저장되어 있는지 확인하고, 있다면 그 값을 즉시 반환합니다. 없다면 계산을 수행한 뒤 그 결과를 캐시에 저장합니다.

이렇게 하면 실행 속도가 훨씬 빨라질 뿐만 아니라, 훨씬 큰 피보나치 수도 계산할 수 있게 됩니다.

재귀의 한계

재귀 방식의 해법은 입력 숫자가 커지면(약 7,500 전후, 정확한 값은 시스템 환경에 따라 다릅니다) SystemStackError: stack level too deep 오류와 함께 실패할 수 있습니다. 이는 호출 스택이 시스템 허용 한도를 초과했기 때문입니다.

그보다 더 큰 숫자를 계산해야 한다면 반복문 기반의 해법을 사용해야 합니다.

예제:

memo = []

(0..n).each do |i|
  memo[i] = i < 2 ? i : memo[i-1] + memo[i-2]
end

세 가지 방식 비교 요약

마무리

재귀는 강력한 프로그래밍 기법이지만, 때로는 머릿속으로 그려내기 어려울 수 있습니다. 이제 직접 코드를 작성하며 연습해 볼 차례입니다. 반복 연습만이 숙달의 지름길입니다!