Swift - 꼬리 재귀 함수

꼬리 재귀 함수는 앞에서 다뤘던 재귀 함수의 단점을 보완하였는데, 일반적인 재귀 함수는 스택이 쌓이고, 호출되지 않을 경우 쌓인 스택을 하나씩 제거합니다. 하지만 꼬리 재귀 함수는 함수를 호출하면서 스택을 재사용하기 때문에 일반적인 재귀 함수에서 발생하는 스택 오버플로우를 예방할 수 있습니다. (값이 매우 커 재귀 함수 호출을 많이 해야 하는 경우 오버플로우 발생 가능성 높음)

 

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

// 꼬리 재귀 함수
func factorial(num: Int, result: Int) -> Int { 
	if num == 1 { return result }
    return factorial(num - 1, num * result)
}

print(factorial(num:3)) // 6
print(factorial(num:3, 1)) // 6

꼬리 재귀 함수의 파라미터를 보면 result가 하나더 추가되어있는 것을 볼 수 있다.

result는 계산되는 결과값을 누적하기 위해 추가되었으며, 마지막 함수 호출시 추가적으로 계산을 진행하지 않고 함수 호출만 하도록 동작한다.