Знайомство з Erlang [4]

У функціональних мовах програмування немає циклів,
натомість існує рекурсія - це коли функція викликає саму себе.

Хвостова рекурсія - це коли рекурсія викликається останньою інструкцією,
таким чином стек залишається незмінним (або ж практично незмінним) і функція може працювати перманентно без зупинки.

Розглянемо приклад двох варіантів (функцій) обчислення факторіалу:

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

%factorial - func2
func2(N) -> func2(N, 1).
func2(0, A) -> A;
func2(N, A) when N > 0 -> func2(N - 1, N * A).

func1 - це рекурсія без хвостої оптимізації,
тобто з "розбуханням" стеку --
чим більше операцій рекурсії - тим більше займе пам'яті дана програма при виконанні;

func2 - хвостова рекурсія, незалежно від кількості операцій - в пам'яті залишаються лише два числа.

Розглянемо приклад двох варіантів (функцій) обчислення чисел Фібоначчі:

%fibonachii - func3
func3(0) -> 0;
func3(1) -> 1;
func3(N) ->
  func3(N - 1) + func3(N - 2).

%fibonachii - func4
func4(N) when N > 0 -> func4(N, 0, 1).
func4(0, F1, _) -> F1;
func4(N, F1, F2) -> func4(N - 1, F2, F1 + F2).

аналогічно:

func3 - це рекурсія без хвостої оптимізації,
тобто з "розбуханням" стеку --
чим більше операцій рекурсії - тим більше займе пам'яті дана програма при виконанні;

func4 - хвостова рекурсія, незалежно від кількості операцій - в пам'яті залишаються лише три числа.

Продовження