Если вы никогда не использовали рекурсию, пора это исправить! Я написал эту статью, чтобы вы разобрались как она работает.
Поняв эту простую концепцию, вы сможете быстро и эффективно решать задачи, которые вынуждают обычных разработчиков идти на поиски ответа в сервисы подобные Stack Overflow.
Что такое рекурсия?
Рекурсия это подход к решению проблемы с использованием функции, которая вызывает себя в качестве подфункции.
Где применяется рекурсия?
- Обход структур данных: объектов, других древовидных структур и т.п.
- Математические операции: вычисление суммы цифр числа, точной степени двойки, разложение на множители и т.п.
- Прикладные задачи: вычисление палиндрома, числа Фибоначи и т.п.
Наша задача
К примеру, у нас есть объект (должников) с большой вложенностью. На каждом уровне вложенности существует ключи, указывающие на имя человека и сумму его долга. Нам нужно посчитать общую задолженность людей из объекта:
Обычный перебор здесь не сработает, ведь он идет только по первому уровню вложенности, а у нас их несколько. На практике мы не можем предугадать на сколько глубокий объект нам попадётся
Именно эту задачу нам и поможет решить рекурсия!
Из чего же состоит рекурсивная функция?
1. Условие, способное остановить самовызов функции
Наша функция должна уметь бесконечно запускать себя. Поэтому должно быть условие, способное завершить бесконечный вызов. Оно должно учитывать 2 случая:
- Бесконечный цикл и последующее переполнение стэка
- Неправильный тип данных и последующее падение функции
Давайте спасем себя от выстрела в ногу, и напишем такие условия:
Они помогут нам избежать бесконечного выполнения функции и переполнения стека вызовов (а если нет ограничения по памяти, то и от зависания браузера). Так же мы предотвратим падение функции, в случае если в неё придут неправильные данные.
2. Условие, способное запустить следующий цикл рекурсии
Такое условие называется «основным», и оно похоже на первое условие, за исключением того, что оно не останавливает, а запускает следующий цикл:
3. Функция должна вызывать себя
После выполнения первых двух условий, нужно замкнуть функцию на себя! Главное не забыть сохранять результат каждого цикла, в том числе рекурсивного:
Сохранять результат можно разными способами, я сделал через оператор присваивания «+=». Чтобы не усложнять код можно сохранять результат во время выполнения основного условия, например, пушить значение в массив находящийся вне области видимости функции.
Для лучшего понимания и применения рекомендую ознакомится с такими понятиями как стек и бинарные деревья.
Итог
Создать рекурсивную функцию для решения вашей задачи достаточно просто, нужно всего лишь соблюдать 3 основных условия: выход из цикла, условие продолжение цикла, замыкание функции на саму себя!