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

Рекурсия и стэк | @alexeycorr

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

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

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

Рекурсия - это метод, при котором функция вызывает саму себя для решения проблемы.

Cтек - это структура данных, которая следует принципу LIFO (last in, first out).

Рекурсия

Для рекурсивного решения задачи, нужно:

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

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

factorial

Stack

Подробнее

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

Стек вызовов
factorial

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

5 * factorial(4)
Стек вызовов
factorial

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

4 * factorial(3)
5 * factorial(4)
Стек вызовов
factorial

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

3 * factorial(2)
4 * factorial(3)
5 * factorial(4)
Стек вызовов
factorial

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

2 * factorial(1)
3 * factorial(2)
4 * factorial(3)
5 * factorial(4)
Стек вызовов
factorial

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

1
2 * factorial(1)
3 * factorial(2)
4 * factorial(3)
5 * factorial(4)
Стек вызовов
factorial

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

2 * 1
3 * factorial(2)
4 * factorial(3)
5 * factorial(4)
Стек вызовов
factorial

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

3 * 2
4 * factorial(3)
5 * factorial(4)
Стек вызовов
factorial

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

4 * 6
5 * factorial(4)
Стек вызовов
factorial

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

5 * 24
Стек вызовов
factorial

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

Стек вызовов
factorial5! = 120

Демо

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

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

Uncaught RangeError: Maximum call stack size exceeded

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

Дерево рекурсии

Время работы

Заключение

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

Presentation Linkedin Telegram @alexeycorr