Swift로 꼬리 재귀 사용하기

Swift로 꼬리 재귀 사용하기

by 오진성

Jul 27 2017

꼬리 재귀 사용하기라는 주제로 let us: Go! 2017 Summer에서 발표된 내용입니다.

소개

꼬리 재귀 사용하기라는 주제로 발표할 오진성이라고 합니다. 꼬리 재귀는 꼬리를 물고 들어가는 뱀과 같은 이미지로 생각하면 쉬우실 겁니다.

팩토리얼 예제

팩토리얼 구하기 예제를 생각해 볼까요? 팩토리얼의 수학적 정의와 알고리즘으로 정의하면 위와 같습니다. 코드로는 n을 받아서 n이 0이면 1을 반환하고 0보다 크면 다시 팩토리얼 n-1과 자신을 곱합니다. 실제로 콜스택이 자라났다가 줄어드는데, 이를 늘어나지 않게 고쳐보겠습니다.

index와 answer라는 함수를 받아서 값을 리턴하는 함수입니다. 겉에 함수를 두 개 중첩했고, 콜스택이 일정하게 유지될 수 있습니다. 이런 방식을 꼬리 재귀라고 부릅니다.

피보나치 예제

피보나치 수열을 다시 생각해보겠습니다. 앞의 두 항을 더한 것을 다음 항으로 하는 수열입니다. 역시 위와 같이 코드로 간단하게 짤 수 있습니다. 하지만 이를 작동하면 트리 모양 재귀가 생겨납니다. 피보나치 5를 부르면 4, 3을, 숫자가 줄어들수록 중복된 호출이 늘어납니다. 실제로 피보나치에 100을 넣으면 실행 속도가 매우 늘어나므로 역시 꼬리 재귀로 바꿔보겠습니다.

3개 인자를 받아서 n이 0이면 a를, 아니면 피보나치에 b, a+b, n-1을 넣어서 하나씩 줄여나가면서 값을 더합니다. 이 경우 3번째 인자의 숫자는 계속 줄어들고, 이것이 0이 되면 반환하도록 했습니다. 100을 넣더라도 100번만 실행되므로 스택 오버플로가 발생할 위험이 없습니다.

스택 오버플로 피하기

이런 개발 뉴스를 더 만나보세요

Swift는 꼬리 재귀가 끝나는 지점에서 콜스택이 끝나도록 컴파일러가 최적화할 수 있는데, 이는 최적화 옵션을 켜줘야 합니다. 꼬리 재귀 방식으로 짰는데 데이터가 많이 들어간다면 꼭 최적화 옵션을 켜주세요. 함수가 복잡해지고 하는 행동이 많아질수록 최적화가 더욱 필요합니다.

핑퐁수열

8퍼센트 면접 문제로 소개된 핑퐁수열 문제를 소개하겠습니다. 1씩 증가하거나 감소하는 수열로 인덱스가 7의 배수이거나 7을 포함하면 방향을 바꾸는 수열입니다. 이런 수열을 for 문이나 배열을 쓰지 않고 문자열과 대입 연산자도 쓰지 않는 제약 사항에서 만드는 함수를 작성하는 문제입니다. 어려워 보이지만 재귀 함수를 사용하면 대입을 피하면서 함수를 만들 수 있습니다.

7의 배수이거나 7을 가졌는지 판별하는 함수를 작성했습니다. 이를 바탕으로 핑퐁 수열도 만들었습니다. 인덱스를 받아서 튜플을 반환하는 함수로, 방향 개념도 넣었습니다. 핑퐁 14를 구하려면 13을, 13을 구하려면 12를 알아야 하는 함수로 1까지 내려갔다가 다시 올라가서 최종값을 구해야 하므로 콜스택이 늘어나는 형태입니다. 아직 꼬리 재귀 형태가 아니죠.

이제 꼬리 재귀로 만들어 보겠습니다. 카운터가 인덱스와 같으면 answer를 반환하고, has7 함수와 함께 꼬리 재귀 형식으로 값을 반환하도록 바꿨습니다. 다시 이를 다른 함수로 감싸서 만들어줬습니다.

꼬리 재귀로 배열 탐색

배열에 있는 모든 원소를 더하는 꼬리 재귀 함수를 만들어 보겠습니다. 함수의 맨 앞을 head로 정하고 나머지를 tail로 지정했습니다. 재귀적으로 다시 tail과 head를 더하는 형식이며 initial에는 연산의 항등원을 넣습니다. 코드에는 덧셈의 항등원인 0을 넣었습니다. tail이 빌 때까지 연산하다가 빈 경우 반환을 하게 됩니다.


func tailRecursive(array: [Int], 
                  initial: Int,
                  eachOperation: (Int, Int) -> Int ) -> Int {
  guard let head = array.first else { return initial }
  let tail = Array(array.dropFirst())
  
  return tailRecursive(array: tail,
                      initial: eachOperation(head, initial),
                      eachOperation: eachOperation)
} 

tailRecursive(array: array,
              initial: 0,
              eachOperation:{(element: Int, answer: Int)->Int in
  element + answer })
  
// ➔ 47

이를 위 코드처럼 tailRecursive라는 함수로 다시 고쳤습니다. initail 자리에는 덧셈 대신 받은 클로저를 넣습니다. 이 함수에 배열을 넣어주고 eachOperation 자리에 값을 두 개 받아서 덧셈하는 클로저를 만들어서 넣어줬습니다. 이렇게 하면 47이라는 값이 나옵니다.

extension Array {
  func tailRecursive<Result>(
    _ initial: Result,
    eachOperation: (Result, Element) -> Result ) -> Result {
      guard let head = self.first else { return initial }
      let tail = Array(self.dropFirst())
      
      return tail.tailRecursive(eachOperation(initial, head),
                                              eachOperation: eachOperation)
    }
  }
}

array.tailRecursive(0, eachOperation: + )

array.tailRecursive(0) { (element: Int, answer: Int) -> Int in
  return element + answer
}

array.reduce(0) { (element: Int, answer) -> Int in
  return element + answer
}

위 코드처럼 좀 더 일반화해서 int형 배열을 general 타입으로 바꾸고 배열의 익스텐션 함수로 넣어서 다시 변경했습니다. 배열 익스텐션 안으로 코드를 넣고 타입을 general로 변환했습니다. 이 경우 아까처럼 클로저를 넣어주면 배열의 함수처럼 사용할 수 있습니다. 이 함수의 모양이 reduce 오퍼레이터가 동일한 것을 눈치채셨나요? Swift의 가장 큰 장점인 map, reduce 중 reduce의 내부가 바로 꼬리 재귀 형태입니다. 그럼 처음으로 돌아가서 팩토리얼을 한 줄로 짜려면 어떻게 할까요?

Array(1...5).reduce(1, *)

그럼 반복문으로 전부 가능하지 않은지 의구심이 들 수 있습니다. 하지만 트리 형태의 경우 반복문으로 접근하기 어려우므로 꼬리 재귀가 적합합니다. 트리 탐색을 이진 탐색을 하는 것도 꼬리 재귀가 적합합니다. 하지만 트리 전체를 탐색하는 것은 꼬리 재귀 방법을 적용하기 좀 까다롭습니다.

그럼 iOS 개발자는 언제 트리를 사용하게 될까요? 뷰 컨트롤러를 쓸 때 탭 컨트롤러가 있고 안에 내비게이션 컨트롤러가 있고 하는 이런 구조가 바로 트리 형태이므로, 최상단 뷰컨트롤러를 찾는 등 자주 쓰는 기능에서도 이런 꼬리 재귀 함수를 사용할 수 있습니다.


func searchTopViewController(viewController: UIViewController?) -> UIViewController? {
  guard let viewController = viewController else { return nil }
  switch viewController {
    case let viewController as UITabBarController:
      return searchTopViewController(viewController: viewController.selectedViewController)
    
    case let viewController as UINavigationController:
      return searchTopViewController(viewController: viewController.viewControllers.last)
    
    case let viewController where viewController.presentedViewController != nil:
      return searchTopViewController(viewController:viewController.presentedViewController)
      
    default:
      return viewController
  }
}

팩토리얼, 피보나치 수열의 일반 재귀와 꼬리 재귀를 말씀드리고 핑퐁 수열과 배열 탐색에 대해 말씀드렸습니다. Swift에서 꼬리 재귀 함수를 사용하시는 데 도움이 되길 바랍니다.

본 영상과 글은 let us: Go!의 비디오 스폰서인 Realm에서 제공합니다. 모바일 개발자가 더 나은 앱을 더 빠르게 만들도록 돕는 Realm 모바일 데이터베이스와 Realm 모바일 플랫폼을 통해 핵심 로직에 집중하고 개발 효율을 높여 보세요! 공식 문서에서 단 몇 분 만에 시작할 수 있습니다. 또한 Realm 홈페이지에서는 모바일 개발자를 위한 다양한 최신 기술 뉴스와 튜토리얼을 제공하고 있으니 즐겨찾기하고 자주 들러 주세요!

다음: Realm Swift를 사용하면 iOS 앱 모델 레이어를 효과적으로 작성할 수 있습니다.