Алгоритм «снова и снова»!
Рекурсия возникает, когда вещь определяется в терминах самой себя или своего типа. Таким образом, по сути, это повторение чего-либо внутри себя… Рекурсия — это понятие, обычно применяемое в математике и информатике, где определяемая функция также применяется в рамках ее собственного определения. Сидя на сеансе парного программирования с Гугу Сибаньони, мы решили, что было бы интересно опубликовать статью об этой умопомрачительной концепции и пролить свет на различные проблемы, которые решает рекурсия.
Фото Grooveland Designs на Unsplash
Есть два типа рекурсии; хвостатая и нехвостая рекурсия. Хвостовая рекурсия возникает, когда рекурсивный вызов выполняется функцией последним. Функции с хвостовой рекурсией считаются лучше, чем функции без рекурсии, поскольку хвостовая рекурсия может быть оптимизирована компилятором. Положительным моментом является то, что мы можем оптимизировать не-хвост, записав их как хвостатую рекурсию.
Факториал целого числа «n» определяется как произведение этого числа на каждое целое число от n до 1. Например, факториал 4 равен 4×3×2×1, что равно 24.
В хвостовой рекурсии мы можем записать факториальную функцию следующим образом
def factorial(n):if __name__ == '__main__':
if (n == 0 or n == 1):
n = 5
print("factorial of", n, "is:", factorial(n))
return 1;
else:
return n * factorial(n - 1);
Преимущество рекурсии или рекурсивного программирования заключается в том, что он обеспечивает чистый и простой способ написания кода, в то время как итеративное программирование дольше и может показаться немного запутанным.
Теперь, когда мы немного знаем о рекурсии, давайте посмотрим, как она может подкрадываться к нам в вопросах на собеседовании.
Знаменитая Ханойская башня, к сожалению, не является башней с сокровищами, включая принцессу… нет…. Это математическая головоломка, в которой у нас есть три стержня и n дисков. Цель головоломки состоит в том, чтобы переместить всю стопку на другой стержень, соблюдая следующие ограничения:
1) Одновременно можно перемещать только один диск.
2) Каждое перемещение состоит в том, чтобы взять верхний диск из одной стопки и поместить его поверх другой стопки. Короче говоря, диск можно переместить только в том случае, если он является самым верхним диском в стопке.
3) Ни один диск не может быть помещен поверх меньшего диска.
def TowerOfHanoi(n , source, destination, auxiliary):n = 3
if n==1:
TowerOfHanoi(n,'A','B','C')
print ("Move disk 1 from source",source,"to destination",destination)
return
TowerOfHanoi(n-1, source, auxiliary, destination)
print ("Move disk",n,"from source",source,"to destination",destination)
TowerOfHanoi(n-1, auxiliary, destination, source)
Знаменитый ряд Фибоначчи… Числа Фибоначчи — это числа в следующей целочисленной последовательности. И по соглашению первые два числа 0, 1.
0, 1, 1, 2, 3, 5, 8, 13, 21…
Если вы посмотрите, вы заметите, что каждое число является суммой двух предыдущих чисел. Мы можем записать это как математическую формулу, и у нас также есть рекурсивная функция.
Fn = Fn-1 + Fn-2
# A tail recursive function to calculate nth fibonacci number def fib(n, a = 0, b = 1):n = 10
if n == 0:
return a
print("fib("+str(n)+") = "+str(fib(n)))
if n == 1:
return b
return fib(n - 1, b, a + b);
О бинарном поиске часто не спрашивают на собеседованиях, но знать об этом стоит. Ограничение двоичного поиска заключается в том, что массив необходимо отсортировать. Внутренняя работа бинарного поиска с использованием рекурсии заключается в том, что вы ищете с обоих концов массива.
Рекурсия очень популярна в задачах сортировки, поэтому мы кратко объясним каждую проблему и предоставим кодовое решение для нее по ссылке ниже.
Групповая сортировка
Сортировка кучей — это метод сортировки на основе сравнения, основанный на структуре данных двоичной кучи. Это похоже на сортировку выбором, где мы сначала находим минимальный элемент и помещаем минимальный элемент в начало. Повторяем тот же процесс для остальных элементов. Heapsort довольно эффективен со средней, наилучшей и наихудшей временной сложностью O (n log n) и пространственной сложностью O (1), однако она не превосходит нашу следующую сортировку — быструю сортировку.
Быстрая сортировка
Быстрая сортировка — это метод внутренней сортировки, при котором данные, обычно массив, сортируются в основной памяти. Метод здесь заключается в том, что мы разделяем и властвуем. Массив элементов многократно делится на части, пока его нельзя разделить дальше, а затем сортируется с использованием опорных точек.
Сортировка слиянием
Сортировка слиянием — это метод внешней сортировки, при котором данные, подлежащие сортировке, не могут быть размещены в памяти, поэтому для сортировки требуется дополнительная память. Это намекает нам, что сортировка слиянием является предпочтительной сортировкой для связанных списков. Метод здесь заключается в том, что мы разделяем и властвуем, но только на два подмассива, и у нас есть третий массив для хранения отсортированного массива.
Аргумент о том, когда использовать быструю сортировку или сортировку слиянием, сводится к использованию быстрой сортировки для небольших массивов или наборов данных и использованию сортировки слиянием для больших массивов, больших наборов данных и связанных списков.
Пожалуйста, ознакомьтесь с кодовыми решениями по ссылке, приведенной ниже.
Дополнительные ресурсы
