Многих при подготовке к собеседованиям интересует, что же спрашивают на собеседованиях на вакансию программиста. Есть вопросы, которые можно встретить не зависимо от языка программирования и уровня (Junior, Middle, Senior). Одним из таких - фундаментальных знаний является понимание, что такое рекурсия.
Многие алгоритмы построены на рекурсивных вызовах функций. Так что же такое рекурсия ?
Возьмем функцию А, которая вызывает сама себя с измененными аргументами. Это пример простой рекурсии. Классический пример это вычисление факториала.
Примечание: Я намеренно не использую типы данных и библиотеки типа "math/big" для работы с большими числами чтобы код был более понятным. На практике, конечно нужно использовать их.
Тут функция calcFactorial является рекурсивной т.к. вызывает сама себя.
Бывают и более сложные случаи, например вычисление чисел Фибоначчи требует 2 вызова функции для вычисление одного числа. Можно назвать это параллельной рекурсией.
N-й член последовательности Фибоначчи определяется по формуле: f(N)=f(N-1) + f(N-2), при условии, что f(0)=0 и f(1)=1.
По своей структуре обычно в рекурсивной функции есть условия прекращения вызова. Всегда стоит заботиться об ограничениях на которых работает рекурсивная функция. Мы должны гарантировать, что через конечное количество вызовов будет достигнуты условия прекращения рекурсии, в результате чего цепочка последовательных рекурсивных вызовов прервётся и будет возвращен результат.
Реализация рекурсии в языках программирования, обычно, реализуется через механизм стека вызовов — адрес возврата и локальные переменные функции записываются в стек, благодаря этому каждый следующий вызов этой функции использует свой набор локальных переменных и поэтому будет работать корректно.
Минусом всего этого простого по своей структуре механизма является то, что на каждый рекурсивный вызов требуется определенное количество оперативной памяти, и при чрезмерно большой глубине рекурсии может наступить переполнение стека вызовов.
Теоретически, работу рекурсивной функции всегда можно заменить применением сочетания цикла и стека.
Итеративные варианты зачастую работают быстрее.
На собеседованиях бывает спрашивают про "хвостовую рекурсию". Это такой частный случай рекурсии когда последним действием в рекурсивной функции будет вызов самой функции этой функции. Многие интерпретаторы и компиляторы поддерживают оптимизацию кода на уровне исполнения. Они находят такие места и заменяют такой вызов итерацией, что экономит ресурсы. Но такой фокус может произойти не с каждой рекурсивной функцией. Например в нашей рекурсивной функции на Рисунок 1 последним действием является умножение
return digit * calcFactorial(digit - 1)
Чтобы сделать из этого примера хвостовую рекурсию, нужно переписать функцию и использовать в аргументах накопитель
Думаю основные мысли я изложил:
- Следите за глубиной рекурсии (обязательно попадание программы в терминальную (не рекурсивную) ветку).
- Хвостовая рекурсия лучше обычной
- Рекурсию можно заменить циклом и стеком