F#의 꼬리 재귀 최적화(Tail Recursion Optimization)

프로그래밍 언어 F#
1

F#은 함수형 프로그래밍을 제공하는 다중 패러다임 언어라고 할 수 있는데요, 다음의 위키 백과를 통해 좀 더 상세하게 F#에 대한 정의를 살펴볼 수 있어요.

F#은 강력한 함수형 프로그래밍을 제공하기 때문에 문제를 분할해서 정복하는 재귀 함수형태는 F#에서 상당히 빈번하게 사용될 수 있는데요, 문제는 재귀 호출에는 비용이 발생한다는 점입니다.

재귀 호출은 함수 호출이 누적되기 때문에 스택을 계속해서 소모하게 되는데 이것이 스레드가 가진 스택 크기를 초과하게 되면 stack overflow가 발생하게 되어요.

그래서 함수형 언어는 꼬리 재귀 최적화를 통해 이런 문제를 해소할 수 있는데요,

C#은 꼬리 재귀 최적화를 제공하지 않아요!

피보나치 수를 구하는 다음의 F# 코드를 통해 살펴볼 수 있어요!

let rec fibonacci n =
    if n <= 1 then n
    else fibonacci (n - 1) + fibonacci (n - 2)

// 예시: 첫 10개의 피보나치 수를 출력
[0..9]
|> List.map fibonacci
|> List.iter (printfn "%d")

이를 다음과 같이 꼬리 재귀 최적화를 통해 최적화 할 수 있어요

let fibonacci n =
    let rec loop a b n =
        if n = 0 then a
        else loop b (a + b) (n - 1)
    loop 0 1 n

// 예시: 첫 10개의 피보나치 수를 출력
[0..9]
|> List.map fibonacci
|> List.iter (printfn "%d")