ublog

Знайомство з erlang: рекурсії

programming [33]erlang [32]

Вітаю!

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

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

Розглянемо функції обчислення факторіалу:

%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 - хвостова рекурсія, незалежно від кількості операцій - в пам'яті залишаються лише два числа


Далі буде)