20

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

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

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

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

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

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

11
  • олимпиады по программированию почитайте разборы или сами порешайте. Можете codeforces.com тут.
    – pavel
    4 мар 2016 в 13:06
  • Я ж написал, что решаю задачи с хакерранка, там абстрактные задачи на понимание алгоритмов, структур данных и методов программирования. В том числе на рекурсию. Как навык-то прокачать, если решить могу только самые простые задачи?
    – typemoon
    4 мар 2016 в 13:09
  • Только тренировки, никаких хитростей тут нету. Чем больше решите задач, тем быстрее будете понимать решение новых.
    – iksuy
    4 мар 2016 в 13:09
  • 1
    @typemoon, вы говорите, что от программирования переходите к математическому описанию. Рекурсия это тоже самое, что и принцип математической индукции. Один в один. 4 мар 2016 в 13:32
  • 2
    Однако и математическая индукция не поможет мне сейчас решить задачу top view. Похоже, у всех возникло непонимание сути проблемы. Предполагаю, что у советчиков создается иллюзия понимания рекурсии, потому что могут написать по памяти merge sort. Но на любой незнакомой задаче они, скорее всего, сольются, потому что могут написать решение только известных им задач. Я хочу научиться решать рекурсивно любую задачу и представлять процесс выполнения рекурсивной функции.
    – typemoon
    4 мар 2016 в 13:36

3 ответа 3

10

Можно представить, что рекурсивная функция уже написана. При решении задачи использовать её как уже написанную. После этого убедиться, что существуют граничные условия, при которых рекурсия остановится.

Например, пусть у нас есть следующая задача: нужно найти число возможных способов размена 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.

5

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

2
  • что означает: функциями высшего порядка (Javascript, Python etc.) не используя при этом переменные. Как это применить в js например?
    – spectre_it
    23 окт 2016 в 8:55
  • 1
    const вместо var? Техник много: map/reduce вместо for, чистые функции, иммутабельные конечные автоматы (напр. redux), unidirection data flow, потоки, генераторы... 23 окт 2016 в 16:02
3

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

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

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

5
  • "В данном случае требуется освоить курс основ алгоритмов" Ваше утверждение неверно. Я изучил и реализовал много алгоритмов, могу написать несколько видов деревьев по памяти, сортировки, систему непересекающихся подмножеств, sqrt-декомпозицию и прочее, а top view решить не могу.
    – typemoon
    4 мар 2016 в 14:09
  • @typemoon - Не переживайте. Это плохо сформулированная задача.
    – user176262
    4 мар 2016 в 14:11
  • Да нет, суть задачи ясна, а как здесь применить рекурсию - непонятно. Несколько моих решений выводят не то, что нужно, или выводят все элементы дерева.
    – typemoon
    4 мар 2016 в 14:14
  • Вам нужны две разные рекурсивные функции. Одна - для левой стороны дерева, другая - для правой. Они будут отличаться лишь местом, в котором выводится значение вершины. В одном случае print будет после рекурсивного вызова, в другом - до.
    – zverkov
    4 мар 2016 в 14:19
  • 1
    @typemoon Тогда, если Вы считаете, что имеющихся у Вас знаний достаточно, то вижу только один способ: сделать паузу в решении задачи - не все задачи удается решить сразу. 4 мар 2016 в 14:20

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими пользовательским соглашением, политикой конфиденциальности и политикой о куки

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.