[Swift] Tail recursion(꼬리 재귀함수)

 

 

Q. Tail recursion이 무엇인지 설명해 줘

 

A. Tail recursion은 함수가 호출된 후, 함수가 실행을 끝내기 전에 마지막으로 다시 자신을 호출하는 재귀 함수의 형태를 말합니다. 이러한 재귀 함수에서는, 함수 호출이 함수 실행이 끝나기 전에 마지막으로 발생하기 때문에, 스택 메모리의 사용을 최적화할 수 있습니다.

 

일반적인 재귀 함수는 함수가 호출될 때마다 새로운 스택 프레임이 생성되어 스택 메모리에 저장됩니다.

이는 재귀 함수의 호출 수가 많아지면 스택 메모리를 많이 사용하게 되어 스택 오버플로우 에러가 발생할 가능성이 있습니다.

 

하지만 Tail recursion의 경우, 함수가 실행을 끝내기 전에 마지막으로 자기 자신을 호출하므로, 스택 프레임을 계속해서 생성하지 않아도 됩니다. 대신에, 현재의 스택 프레임을 재사용할 수 있습니다. 이를 통해 스택 메모리 사용을 최적화하고, 스택 오버플로우 에러를 방지할 수 있습니다.

 

예를 들어, 다음은 일반적인 재귀 함수와 Tail recursion 함수의 예입니다.

# 일반적인 재귀 함수
def factorial(n):
    if n == 0:
        return 1
    else:
        return n * factorial(n-1)
        
# tail recursion 함수
def factorial(n, acc=1):
    if n == 0:
        return acc
    else:
        return factorial(n-1, acc * n)

일반적인 재귀 함수에서는, 매번 호출될 때마다 새로운 스택 프레임이 생성되어 스택 메모리를 차지합니다.

하지만 Tail recursion 함수에서는, 이전의 스택 프레임을 재사용하기 때문에 스택 메모리 사용을 최적화할 수 있습니다.

 

 

Q. 위 예시를 Swift 코드로 설명해 줘

 

A. Swift 코드로 위의 예시를 설명해 보겠습니다.

// 일반적인 재귀 함수
func factorial(_ n: Int) -> Int {
    if n == 0 {
        return 1
    } else {
        return n * factorial(n-1)
    }
}

// tail recursion 함수
func factorial(_ n: Int, _ acc: Int = 1) -> Int {
    if n == 0 {
        return acc
    } else {
        return factorial(n-1, acc * n)
    }
}

일반적인 재귀 함수는 매번 호출될 때마다 새로운 스택 프레임을 생성합니다.

따라서, factorial(5)를 호출하면 다음과 같이 스택에 쌓이게 됩니다.

factorial(5)
factorial(4)
factorial(3)
factorial(2)
factorial(1)
factorial(0)

 

하지만 tail recursion 함수는 스택 프레임을 재사용하기 때문에 스택 메모리 사용을 최적화할 수 있습니다.

따라서, factorial(5)를 호출하면 스택에 단 한 개의 프레임만 남게 됩니다.

factorial(5, 1)

이렇게 스택 프레임을 재사용하면, 매우 깊은 재귀 함수를 호출할 때에도 스택 오버플로우 에러를 방지할 수 있습니다.

 

 

 

Q. 일반적인 재귀 함수 대신 tail recursion을 사용하려면 어떻게 해야 하니?

 

A. 일반적인 재귀 함수 대신 tail recursion을 사용하려면 다음과 같은 방법을 고려할 수 있습니다.

 

1. 함수를 작성할 때, tail recursion 형태로 작성합니다.

- 함수가 호출된 후, 함수가 실행을 끝내기 전에 마지막으로 다시 자신을 호출하는 형태로 작성합니다.

- 이를 통해, 함수 호출이 함수 실행이 끝나기 전에 마지막으로 발생하므로 스택 프레임을 재사용할 수 있습니다.

 

2. 컴파일러 최적화 기능을 사용합니다.

- 대부분의 최신 컴파일러는 tail recursion 함수를 인식하고, 스택 메모리 사용을 최적화하는 최적화 기능을 제공합니다.

- 따라서, 컴파일러 최적화 기능을 사용하면 일반적인 재귀 함수보다 더 효율적인 코드를 생성할 수 있습니다.

 

3. 꼬리 재귀 최적화(tail call optimization)를 지원하는 언어를 사용합니다.

- 몇몇 언어는 꼬리 재귀 최적화를 지원합니다.

- 이 경우, 컴파일러가 tail recursion 함수를 인식하고, 스택 메모리 사용을 최적화하는 코드를 생성합니다.

- 예를 들어, Swift 언어는 꼬리 재귀 최적화를 지원합니다.

 

따라서, tail recursion 함수를 작성하고 컴파일러 최적화 기능을 사용하거나, 꼬리 재귀 최적화를 지원하는 언어를 사용하는 것이 일반적인 재귀 함수보다 더 효율적인 코드를 작성할 수 있는 방법입니다.

 

 

 

Q. Swift를 활용해서 꼬리 재귀 최적화를 활용하는 방법과 예시를 알려줘

 

A. Swift는 꼬리 재귀 최적화를 지원하기 때문에, tail recursion 함수를 작성하면 컴파일러가 최적화하여 스택 메모리를 최적화합니다.

다음은 Swift에서 꼬리 재귀 최적화를 사용하여 팩토리얼을 계산하는 예시입니다.

 

func factorial(_ n: Int) -> Int {
    func tailFactorial(_ n: Int, _ acc: Int) -> Int {
        if n == 0 {
            return acc
        } else {
            return tailFactorial(n-1, acc * n)
        }
    }
    
    return tailFactorial(n, 1)
}

print(factorial(5)) // 출력 결과: 120

위의 코드에서, tailFactorial 함수는 tail recursion 형태로 작성됩니다.

이 함수에서는 현재 스택 프레임을 재사용하기 때문에 스택 메모리 사용을 최적화할 수 있습니다.

이를 통해, 매우 큰 입력값에 대해서도 스택 오버플로우 에러를 방지할 수 있습니다.

 

꼬리 재귀 최적화를 사용하면, 일반적인 재귀 함수보다 더 효율적인 코드를 작성할 수 있습니다.

하지만, Swift는 모든 종류의 재귀 함수를 최적화하지는 않기 때문에, 불필요한 재귀 함수 호출을 제거하여 스택 메모리를 최적화하는 것이 중요합니다.

 

 

Q. Swift로 Factorial을 구현할 때 일반적인 재귀 함수와 꼬리 재귀 함수의 시간 복잡도는 각각 어떻게 되니?

 

A. 일반적인 재귀 함수와 꼬리 재귀 함수의 시간 복잡도는 같습니다. 둘 다 O(n)입니다.

 

하지만, 일반적인 재귀 함수의 경우, 함수 호출이 많아지면 스택 메모리를 많이 사용하게 되므로, 스택 오버플로우 에러가 발생할 가능성이 있습니다. 반면에, 꼬리 재귀 함수의 경우, 스택 프레임을 계속해서 재사용하기 때문에, 스택 메모리 사용을 최적화할 수 있으며, 스택 오버플로우 에러가 발생하지 않습니다.

 

따라서, 꼬리 재귀 함수를 사용하면 일반적인 재귀 함수보다 더 효율적인 코드를 작성할 수 있습니다.

 

 

Q. Swift 코드로 Fibonacci 함수를 일반적인 재귀 함수와 꼬리 재귀 함수로 구현하는 방법을 모두 보여줘

 

A. 아래는 Swift 코드로 Fibonacci 함수를 일반적인 재귀 함수와 꼬리 재귀 함수로 각각 구현한 예시입니다.

 

일반적인 재귀 함수로 Fibonacci 함수 구현하기

func fibonacci(_ n: Int) -> Int {
    if n <= 1 {
        return n
    } else {
        return fibonacci(n-1) + fibonacci(n-2)
    }
}

print(fibonacci(10)) // 55 출력

일반적인 재귀 함수에서는 fibonacci 함수가 자기 자신을 재귀적으로 호출하면서 계산을 수행합니다.

이때, 중복되는 계산이 많이 일어나게 되므로, 입력값이 커질수록 계산 시간이 길어지게 됩니다.

 

꼬리 재귀 함수로 Fibonacci 함수 구현하기

func fibonacci(_ n: Int) -> Int {
    func tailFibonacci(_ n: Int, _ a: Int, _ b: Int) -> Int {
        if n == 0 {
            return a
        } else {
            return tailFibonacci(n-1, b, a+b)
        }
    }
    
    return tailFibonacci(n, 0, 1)
}

print(fibonacci(10)) // 55 출력

꼬리 재귀 함수에서는, 계산 과정에서 중복되는 계산이 발생하지 않도록 tailFibonacci 함수에서 이전 값을 파라미터로 전달받아 계산을 수행합니다. 이렇게 중복 계산을 피할 수 있으므로, 입력값이 커져도 빠른 계산이 가능합니다.

 

위 코드에서 tailFibonacci 함수는 n번째 피보나치 수를 계산하는데 필요한 두 개의 값을 파라미터로 전달받습니다.

초기값으로는 a는 0, b는 1로 설정하고, n이 0이 될 때까지 값을 계속해서 갱신하면서 계산합니다.

 

이렇게 꼬리 재귀 함수를 사용하면, 일반적인 재귀 함수보다 계산 속도가 더 빠르고, 입력값이 커져도 스택 오버플로우 에러가 발생하지 않습니다.

 

* 막상 ChatGPT가 알려준 꼬리 재귀 함수 방법으로 프로그래머스의 피보나치 문제(레벨 2)를 풀어보니 테스트 케이스는 통과하였으나 채점 과정에서는 시간 초과가 발생하였습니다,,, 이 점 참고하십시오...ㅋㅋ

 

 

 

Q. 두 방법이 시간 복잡도도 다른 거야?

 

A. 일반적인 재귀 함수와 꼬리 재귀 함수의 시간 복잡도는 같습니다. Fibonacci 수열의 경우, 일반적인 재귀 함수와 꼬리 재귀 함수 모두 O(2^n)의 시간 복잡도를 갖습니다.

 

하지만, 중복 계산을 피하고 스택 오버플로우 에러를 방지할 수 있는 꼬리 재귀 함수를 사용하면, 일반적인 재귀 함수보다 더 효율적인 코드를 작성할 수 있습니다. 따라서, 입력값이 커질수록 꼬리 재귀 함수가 더 빠른 계산을 할 수 있습니다.

 

 

 

Q. 모든 재귀 함수를 꼬리 재귀 함수 형태로 변경해서 사용할 수 있는 거니?

 

A. 모든 재귀 함수를 꼬리 재귀 함수 형태로 변경해서 사용할 수 있는 것은 아닙니다.

꼬리 재귀 함수 형태로 변경할 수 있는 함수는 다음 조건을 만족해야 합니다.

 

1. 함수가 자신을 호출하는 부분이 함수의 마지막 부분에 있어야 합니다.

- 즉, 함수 호출 이후에 다른 계산이 없는 형태여야 합니다.

 

2. 함수가 값을 반환하는 부분에서 재귀 호출의 결과를 바로 반환하거나, 반환 값을 다른 함수의 인자로 전달해야 합니다.

- 즉, 반환 값을 계산하여 다른 계산을 수행하지 않아야 합니다.

 

위 조건을 만족하지 않는 재귀 함수는 꼬리 재귀 함수 형태로 변경할 수 없습니다.

따라서, 일부 재귀 함수는 일반적인 재귀 함수 형태로 구현해야 하며, 이때는 스택 오버플로우 에러를 방지하기 위해 재귀 호출 수를 제한하는 등의 방법을 고려해야 합니다.