Как научиться писать рекурсивные алгоритмы

Как развить рекурсивное мышление до уровня, на котором можно было бы легко решать
задачи типа вывода только тех элементов бинарного дерева, которые видны с вершины,
и легко писать прочие рекурсивные алгоритмы, например, динамического программирования?

Гуглится только либо чушь, либо примитивные объяснения про "карач рекурсия это када
функция вызывает сама себя)))". Реже попадается информация о том, как используется
стек при работе рекурсивных процедур, но это знание никак не повышает способность писать
рекурсивные алгоритмы.

Решения нескольких задач на рекурсию с хакерранка мне пришли интуитивно, а я хочу
развить способность решать произвольную задачу на рекурсию осознанно. Как этого добиться?

Примеры типа:

def f(n):
    if(n == 0) return
    print n
    f(n - 1)


примитивны, чересчур легки, и их понимание не развивает способность решить заданную
задачу рекурсивно.
    

Ответы

Ответ 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.


Ответ 2

Практикой. Можно конечно вывести Y-Combinator, но также решайте ежедневные задачи
на своём любимом языке с функциями высшего порядка (Javascript, Python etc.) не используя
при этом переменные. Это снизит мутагенность и энтропию  ваших программ, к тому-же.
По-возможности, пишите на Scheme (практичные приложения: Guile, lambdanative), но тоже
без set!, и конечно на Haskell. Т.к. то, что вы назвали "рекусивным мышлением", по
сути является практикой приложения лямбда-исчисления, то и проще всего воспринять это
из уже сложившейся инфраструктуры чисто-функционального языка.


Ответ 3

Чтобы решать задачи (в любой области) необходимы знания и практика.
В данном случае требуется освоить курс основ алгоритмов: прочитать (или прослушать)
и решить не одну задачу.

В качестве такого курса можно порекомендовать книгу Седжвик. Алгоритмы на C++. Фундаментальные
алгоритмы и структуры данных. (также есть варианты этой книги для C и Java). В ней,
в частности, есть и глава, посвященная рекурсии, и довольно много упражнений.

А после изучения основ умение выбирать более оптимальные решения приходит с опытом.