Опять работа?!

Рекурсия и стек

Рекурсия

Факториал числа

5! = 1 * 2 * 3 * 4 * 5 = 120

• Базовый случай - n === 1
• Простая функция - n * factorial(n - 1)
• Хранилице - 📚

Stack

1. Глобальный контекст выполнения.
   Используемый по умолчанию. Если говорить про браузер, то там создается объект window и на него будет указывать this.
2. Контекст выполнения функции.
   Каждый раз, когда вызывается функция, для неё создаётся новый контекст.

Как это работает?

Стек вызовов

Как это работает?

5 * factorial(4)

Стек вызовов

Как это работает?

4 * factorial(3)

5 * factorial(4)

Стек вызовов

Как это работает?

3 * factorial(2)

4 * factorial(3)

5 * factorial(4)

Стек вызовов

Как это работает?

2 * factorial(1)

3 * factorial(2)

4 * factorial(3)

5 * factorial(4)

Стек вызовов

Как это работает?

1

2 * factorial(1)

3 * factorial(2)

4 * factorial(3)

5 * factorial(4)

Стек вызовов

Как это работает?

2 * 1

3 * factorial(2)

4 * factorial(3)

5 * factorial(4)

Стек вызовов

Как это работает?

3 * 2

4 * factorial(3)

5 * factorial(4)

Стек вызовов

Как это работает?

4 * 6

5 * factorial(4)

Стек вызовов

Как это работает?

5 * 24

Стек вызовов

Как это работает?

Стек вызовов

5! = 120

Демо

Преимущества и недостатки

Глубина рекурсии

Uncaught RangeError: Maximum call stack size exceeded

Сложность рекурсии

• Простая рекурсия - O(N)
• Многократная рекурсия - O(N^2) O(2^N)

Заключение

• Хорошо подходит для обработки рекурсивных структур данных, таких как деревья или связанные списки
• Очень быстро можно упереться в максимальную глубину рекурсии
• В случае многократной рекурсии получаем офигеть какую сложность
• Для большого количества данных лучше воспользоваться итеративным подходом

Подписывайтесь, ставьте лайки!

Presentation Linkedin Telegram @alexeycorr