Как научиться писать рекурсивные алгоритмы
1,00
р.
Как развить рекурсивное мышление до уровня, на котором можно было бы легко решать задачи типа вывода только тех элементов бинарного дерева, которые видны с вершины, и легко писать прочие рекурсивные алгоритмы, например, динамического программирования?
Гуглится только либо чушь, либо примитивные объяснения про "карач рекурсия это када функция вызывает сама себя)))". Реже попадается информация о том, как используется стек при работе рекурсивных процедур, но это знание никак не повышает способность писать рекурсивные алгоритмы.
Решения нескольких задач на рекурсию с хакерранка мне пришли интуитивно, а я хочу развить способность решать произвольную задачу на рекурсию осознанно. Как этого добиться?
Примеры типа:
def f(n): if(n == 0) return print n f(n - 1)
примитивны, чересчур легки, и их понимание не развивает способность решить заданную задачу рекурсивно.
Ответ
Можно представить, что рекурсивная функция уже написана. При решении задачи использовать её как уже написанную. После этого убедиться, что существуют граничные условия, при которых рекурсия остановится.
Например, пусть у нас есть следующая задача: нужно найти число возможных способов размена 100 рублей монетами 10 рублей, 5 рублей, 2 рубля и 1 рубль.
То есть нам надо написать функцию f(сумма, набор_монет), которую мы сможем вызвать так: result = f(100, [10, 5, 2, 1]). Первый аргумент - сумма, которую нам надо разменять, а второй - список из уникальных монет, с помощью которых можно представить эту сумму.
Представим, что функция f уже написана. Как теперь мы можем ей воспользоваться? Ключевой момент: придумаем способ разделения возможных вариантов, желательно простой.
Например, заметим, что 100 рублей можно разменять как с использованием десятирублёвой монеты, так и без использования десятирублёвой монеты. Эта идея, можно сказать, и есть решение задачи.
Сумма этих вариантов будет равна искомому числу. Тогда реализацию функции f можно записать как сумму рекурсивных вызовов самой себя с "укороченными" аргументами: f(90, [1, 2, 5, 10]) + f(100, [1, 2, 5]).
f(90, [1, 2, 5, 10]) - мы как бы "забрали" десятирублёвую монету из 100, но не ограничиваем дальнейший выбор монет
f(100, [1, 2, 5]) - мы ничего не забрали из суммы, но ограничили набор монет.
Оба слагаемых вызываются рекурсивно. При этом видно, что количество вариантов будет уменьшаться с каждым рекурсивным вызовом.
Остаётся добавить граничные условия, чтобы функция не вызывалась бесконечно. Для этого нужно определить, при каких аргументах возвращать 1, а при каких - 0.
Гуглится только либо чушь, либо примитивные объяснения про "карач рекурсия это када функция вызывает сама себя)))". Реже попадается информация о том, как используется стек при работе рекурсивных процедур, но это знание никак не повышает способность писать рекурсивные алгоритмы.
Решения нескольких задач на рекурсию с хакерранка мне пришли интуитивно, а я хочу развить способность решать произвольную задачу на рекурсию осознанно. Как этого добиться?
Примеры типа:
def f(n): if(n == 0) return print n f(n - 1)
примитивны, чересчур легки, и их понимание не развивает способность решить заданную задачу рекурсивно.
Ответ
Можно представить, что рекурсивная функция уже написана. При решении задачи использовать её как уже написанную. После этого убедиться, что существуют граничные условия, при которых рекурсия остановится.
Например, пусть у нас есть следующая задача: нужно найти число возможных способов размена 100 рублей монетами 10 рублей, 5 рублей, 2 рубля и 1 рубль.
То есть нам надо написать функцию f(сумма, набор_монет), которую мы сможем вызвать так: result = f(100, [10, 5, 2, 1]). Первый аргумент - сумма, которую нам надо разменять, а второй - список из уникальных монет, с помощью которых можно представить эту сумму.
Представим, что функция f уже написана. Как теперь мы можем ей воспользоваться? Ключевой момент: придумаем способ разделения возможных вариантов, желательно простой.
Например, заметим, что 100 рублей можно разменять как с использованием десятирублёвой монеты, так и без использования десятирублёвой монеты. Эта идея, можно сказать, и есть решение задачи.
Сумма этих вариантов будет равна искомому числу. Тогда реализацию функции f можно записать как сумму рекурсивных вызовов самой себя с "укороченными" аргументами: f(90, [1, 2, 5, 10]) + f(100, [1, 2, 5]).
f(90, [1, 2, 5, 10]) - мы как бы "забрали" десятирублёвую монету из 100, но не ограничиваем дальнейший выбор монет
f(100, [1, 2, 5]) - мы ничего не забрали из суммы, но ограничили набор монет.
Оба слагаемых вызываются рекурсивно. При этом видно, что количество вариантов будет уменьшаться с каждым рекурсивным вызовом.
Остаётся добавить граничные условия, чтобы функция не вызывалась бесконечно. Для этого нужно определить, при каких аргументах возвращать 1, а при каких - 0.
