Заметки:
- Рекурсия — метод вызывает сам себя. Решение с рекурсией становится более понятным.
- Цитата Ли Колдуэлла (https://stackoverflow.com/questions/72209/recursion-or-iteration/72694#72694): "Циклы могут ускорить работу программы. Рекурсия может ускорить работу программиста. Выбирайте, что важнее в вашей ситуации".
- Рекурсия не ускоряет работу. Решение с циклами иногда работает быстрее. По памяти циклы выгодней.
- С рекурсией легко ошибиться и написать метод так, что возникнет бесконечный цикл. Поэтому рекурсивный метод ВСЕГДА состоит из базового случая и рекурсивного.
- Базовый случай — вариант, когда функция себя НЕ вызывает, чтобы не было бесконечного цикла.
- Рекурсивный случай — функция вызывает сама себя.
Стек:
- Стек — это как стопка листков. Новые листочки мы кладем только сверху. И берем тоже сверху.
- В стеке всего два действия: вставка (кладем листок) и чтение (достаем листок).
- Для методов используется стек вызовов и все методы кладутся в этот стек.
Например, есть у нас метод fun addName() { val name = getName() }. При вызове addName() выделяется блок памяти для этого метода. Там будут храниться все переменные и их значения. Когда доходим до метода getName(), то он кладется сверху на метод addName в памяти (прям как лист бумаги). При завершении метода getName он выкидывается из памяти. Но получается, что во время работы getName, метод addName всё ещё существует и не завершен. Он занимает своё место в памяти. - Когда мы вызываем метод из другого метода, то вызывающий метод приостанавливается в частично завершенном состоянии. :)
- Рекурсивные функции используют стек вызовов.
- Попробуем вычислить факториал через рекурсию. Напомню, что факториал — произведение всех предыдущих чисел, включая текущее, но исключая 0. Например, факториал для 3 = 3 * 2 * 1 = 6.
Интересный факт, что каждый раз создается своя копия для number. Обратиться к number из другого метода нельзя.
Минус использования рекурсии: вся промежуточная информация сохраняется в стеке и ведет к затратам памяти. В какой-то момент придется переписать код на циклы или использовать некую хвостовую рекурсию, но в книге решили не рассказывать про неё.
