[Swift Algorithm Note] 꼬리 재귀 함수 (feat. Fibonacci)

저번 글에서 재귀 함수에 대해 다뤘다면, 이번엔 '꼬리' 재귀 함수에 대해 정리해보려고 한다.

피보나치 수를 구하는 함수를 구현해보면서, 재귀함수의 문제점을 알게 되었다.

그런데 이 문제점을 꼬리 재귀 함수가 해결해 준다는 사실을 알게 되었다,,!!

따라서 오늘은 꼬리 재귀 함수를 공부해보고, 구현 방법까지 확실히 이해해보자.

 

📎 꼬리 재귀 함수(Tail Recursive Call)

꼬리 재귀 함수는 일반적인 재귀 함수의 단점을 보완한다.

 

일반적인 재귀 함수가 가지는 단점은 바로

스택 오버플로우가 발생할 수 있다는 점,,!!!💥

 

일반 재귀의 경우, 저번 글에서 다뤘듯

스택에 함수 호출을 하나씩 쌓고, 거꾸로 반환 값을 넘기며 계산을 수행한다.

(이 내용은 요기👇 글을 참고해주세요!)

2021.07.08 - [📍 Algorithm Note/🔍 with Swift] - [Swift Algorithm Note] 재귀함수 정리 (feat. Factorial)

[Swift Algorithm Note] 재귀함수 정리 (feat. Factorial)

 

값이 너무 커서 함수 호출을 아~주 많이 해야 할 경우에는 스택 오버플로우가 발생할 수 있는 것이다.

👉 이러한 점을 보완하고, 재귀 함수의 장점은 살리는 방법이 바로 꼬리 재귀이다.

 

말로 설명하기보다,

재귀 함수의 대표격인 팩토리얼 함수의 일반 재귀, 꼬리 재귀 구현을 보며 이해해보자.

// 일반 재귀
func Recursion(_ x: Int) -> Int {
    if x == 1 { return 1 }
    return x * Recursion(x-1)
}

// 꼬리 재귀
func tailRecursion(_ x: Int, _ result: Int) -> Int {
    if x == 1 { return result }
    return tailRecursion(x-1, x * result)
}

print(Recursion(3)) // 6
print(tailRecursion(3, 1)) // 6

📌 두 재귀 함수의 차이점

1. 파라미터가 하나 더 추가되었다.
   : 하나의 추가된 파라미터는 계산의 누적을 담기 위함이다.
2. 마지막 문장의 재귀 방식에 차이가 있다.
   : 일반 재귀는 함수의 호출과 새로운 계산식이 더해졌다. 하지만 꼬리 재귀는 함수 호출만이 존재한다.
   (꼬리 재귀는 return 문에서 추가 계산 없이 함수 호출만으로 끝내기 위해
   1번 문항 계산 누적 용도의 파라미터를 추가한 것이다.)

여기서 잠깐,

위에서 꼬리 재귀는 일반 재귀의 스택 오버플로우 발생 가능성을 극복하기 위한 방법이라고 명시했다.

하지만 코드로 봐서는 비슷한 로직처럼 느껴진다,,

그림으로 두 함수의 진행 방식을 자세히 살펴보자.

 

📌 두 재귀 함수의 진행 방식

✔️일반 재귀 함수

일반 재귀 함수 진행 방식

일반적인 재귀 함수는 저번 글에서 공부했듯

스택에 차례대로 함수 호출을 쌓고, 반환 값을 LIFO 순서로 전달하며 계산하여

최종 결과를 반환하는 방식이다.

 

✔️ 꼬리 재귀 함수

꼬리 재귀 함수 진행 방식

꼬리 재귀 함수는 스택을 쌓지 않고,

두 번째 인자에 계산 값을 누적하며 전달하는 방식이다.

계속 누적하다가, 마지막에 if문에 걸리면 누적 인자 값을 반환한다!

👉 스택을 사용하지 않아 스택 오버플로우가 발생할 위험이 없다. !!

 

그럼 이제 문제의 피보나치 함수를 꼬리 재귀로 구현해보자,,!!!!!

내가 이 글을 쓰게 된 계기가 바로 피보나치이다.,,

재귀를 공부하고, 피보나치 문제를 다시 보니 재귀로 풀면 좋을 것 같아 바로 해봤는데,,

오류가 야무지게 발생하여,, 이유를 찾다가 여기까지 왔다.

---

📎 피보나치 수 계산 구현

피보나치 수를 구하는 함수를 일반 재귀, 꼬리 재귀를 이용해 각각 구현했다.

// 일반 재귀
func Fibo(_ n: Int) -> Int {
    if n == 0 || n == 1 { return n }
    return Fibo(n - 1) + Fibo(n - 2)
}

// 꼬리 재귀
func tailFibo(_ num: Int, _ n: Int, _ sum: Int) -> Int {
    if num == 1 { return sum }
    return tailFibo(num - 1, sum, n + sum)
}

print(tailFibo(5, 0, 1))
print(Fibo(5))

일반 재귀의 경우, 위의 예시처럼 작은 수의 피보나치를 구할 때는 문제가 없지만

함수 호출을 아주 많이 반복해야 하는 상황에서는 오류가 발생한다.

 

꼬리 재귀의 경우에는 맨 뒤 인자 sum에 누적된 계산 결과를 반환한다.

따라서 스택을 쌓을 필요도, 스택 오버플로우 발생 가능성도 사라진다.

---

👀 정리

꼬리 재귀 함수는 일반 재귀 함수의 단점을 보완한다.

함수 호출 스택을 쌓는 대신 파라미터를 추가하여 계산을 누적한다.

 

---

참고

• https://minsone.github.io/programming/tail-recursion-in-swift
• https://the-brain-of-sic2.tistory.com/33
• https://joooing.tistory.com/entry/%EC%9E%AC%EA%B7%80-%E2%86%92-%EA%BC%AC%EB%A6%AC-%EC%9E%AC%EA%B7%80-Tail-Recursion