Знакомство с Erlang. Часть 2.

Вычисление факториала

Книжный пример. Тут все просто и понятно:

factorial(0) -> 1;
factorial(N) ->
    N * factorial(N-1).

Вычисление чисел Фибоначчи

Пишу реализацию в лоб в надежде, что интерпретатор Erlang внутри реализует DP.

fib(0) -> 0;
fib(1) -> 1;
fib(N) ->
    fib(N-1) + fib(N-2).

Но уже при N=50 не могу дождаться результата. Выходит, никакого DP внутри нет, интерпретатор тупо уходит в рекурсию. Экспоненциальная сложность. Конечно, можно исправить на хвостовую рекурсию, но это уже не так красиво:

fib_ex(1) -> {1, 0};
fib_ex(2) -> {1, 1};
fib_ex(Num) ->
    {P, PP} = fib_ex(Num-1),
    {P + PP, P}.

fib(N) ->
    {P, _PP} = fib_ex(N),
    P.