Содержание

Рекурсивное программирование

При первом знакомстве с концепцией рекурсии, она может показаться странной и отталкивающей. Это кажется почти парадоксальным: как мы можем найти решение проблемы, используя решение той же проблемы? Несмотря на это, в большинстве проектов, рекурсию используют в программировании уже на ранних стадиях производства.

От рекурсии может заболеть голова

Я думаю, что тем, кто пытается постигнуть концепцию рекурсии, следует сначала понять, что рекурсия — это больше, чем просто практика в программировании. Это философия решения проблем, которые можно решать частями, не трогая основную часть проблемы, при этом, проблема упрощается или становится меньше. Рекурсия применима не только в программировании, но и в простых повседневных задачах. Например, возьмите меня, пишущего эту статью: допустим, я хочу написать около 1000 слов, и ставлю цель писать 100 слов каждый раз, когда сажусь за работу. Получается, что в первый раз я напишу 100 слов и оставляю 900 слов на потом. В следующий раз я напишу ещё 100 слов, а оставлю 800. Я буду продолжать, пока не останется 0 слов. Каждый раз, я частично решаю проблему, а оставшаяся часть проблемы уменьшается.

Работу над статьей можно представить в виде такого кода:

write_words(words_left):
if words left > 0:
write_100_words()
words_left = words_left - 100
write_words(words_left)

Также, этот алгоритм можно реализовать итеративно:

write_words(words_left):
while words_left > 0:
write_100_words()
words_left = words_left - 100

Если рассматривать вызов функции write_words(1000) в любой из этих реализаций, вы обнаружите, одинаковое поведение. На самом деле, каждую задачу, которую можно решить с помощью рекурсии, мы также можем решить с помощью итерации (циклы forи while). Так почему же стоит использовать именно рекурсию?

Я пишу статью рекурсивно

Почему рекурсия?

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

Иногда рекурсия более эффективна, иногда более читаема, а иногда просто быстрее реализуется. Некоторые структуры данных, такие как деревья ― хорошо подходят для рекурсивных алгоритмов. Существуют языки программирования, в которых вообще нет понятия цикла — это чисто функциональные языки, такие как Haskell, они полностью зависят от рекурсии для итеративного решения задач. Я хочу сказать, что программисту не обязательно понимать рекурсию, но хороший программист, просто обязан в этом разбираться. Более того, понимание рекурсии сделает вас отличным «решателем» проблем, не только в программировании!

Суть рекурсии

В общем, рекурсивный подход подразумевает разделение сложной задачи, на один простой шаг к её решению и оставшуюся часть, которая становится упрощённой версией той же задачи. Затем этот процесс повторяется. Каждый раз вы совершаете один шаг, до тех пор, пока задача упростится до одного простейшего решения (его называют «базовым случаем»). Простейшее решение нашего базового случая с шагами, которые мы предприняли, чтобы добраться до него, образуют решение нашей первоначальной задачи.

Мы каждый раз разделяем задачу «P» на шаги и оставшуюся упрощённую задачу той же формы, что и оригинал, пока не достигнем простого решения небольшой проблемы (базовый случай).

Предположим, у нас есть фактические данные определённого типа, назовём их dₒ. Идея рекурсии состоит в том, чтобы предположить, что мы уже решили задачу или вычислили желаемую функцию f для всех форм этого типа данных. Каждая из этих форм проще общей сложности dₒ, которую нам нужно определить. Следовательно, если мы можем найти способ выражения 

f(dₒ), исходя из одной или нескольких частей f(d), где все эти d проще, чем dₒ, значит мы нашли решение для f(dₒ). Мы повторяем этот процесс, и рассчитываем, что в какой-то момент оставшиеся f(d) станут настолько простыми, что мы сможем легко реализовать фиксированное, окончательное решение для них. В итоге, решением исходной задачи станет поэтапное решение более простых задач.

В приведённом выше примере (про написание статьи), данными является текст, содержащийся в документе, который я должен написать, а степень сложности — это длина документа. Это немного надуманный пример, но если предположить, что я уже решил задачу f(900)

 (написать 900 слов), то все, что мне нужно сделать, чтобы решить f(1000), ― это написать 100 слов и выполнить решение для 900 слов, f(900).

Давайте рассмотрим пример получше: с числами Фибоначчи, где 1-е число равно 0, второе равно 1, а nᵗʰ число равно сумме двух предыдущих. Предположим, у нас есть функция Фибоначчи, которая сообщает нам nᵗʰ число:

fib(n):
if n == 0:
return 0
if n == 1:
return 1
else:
return fib(n-1) + fib(n-2)

Как будет выглядеть выполнение такой функции? Возьмём для примера fib(4):

Визуализация древа рекурсии, показывающая рекурсивное вычисление, которое приводит к fib(4) = 3. Обратите внимание, что вычисление сначала выполняется в глубину.

В процессе рекурсивного решения задачи полезно повторять мантру: «Притворяйся, пока это не станет правдой», то есть делай вид, что ты уже решил более простую часть задачи.

Затем попытайся уменьшить большую часть задачи, чтобы использовать решение упрощённой части. Подходящая для рекурсии задача, на самом деле должна иметь небольшое количество простых частей, которые нужно решить явно. Другими словами, метод сокращения до более простой задачи может быть использован для решения любого другого случая. Это можно проиллюстрировать на примере чисел Фибоначчи, где для определения fib(n) мы действуем, как будто мы уже рассчитали fib(n-1) и fib(n-2). В тоже время мы рассчитываем, что эти каскады и упрощения приведут к более простым случаям, пока мы не достигнем fib(0) и fib(1), которые имеют фиксированные и простые решения.

«Притворяйся, пока это не станет правдой»

Рекурсивная стратегия

Рекурсивный подход — дело тонкое, и зависит от того, какую проблему вы пытаетесь решить. Тем не менее, есть некоторая общая стратегия, которая поможет вам двигаться в правильном направлении. Эта стратегия состоит из трёх шагов:

  1. Упорядочить данные
  2. Решить малую часть проблемы
  3. Решить большую часть проблемы

Как я уже говорил, я думаю, что для обучения полезно приводить пример, но помните, что рекурсивный подход зависит от конкретной задачи. Поэтому старайтесь сосредоточиться на общих принципах. Мы рассмотрим простой пример с реверсом строки. Мы напишем функцию reverse,которая будет работать так: reverse('Hello world') = 'dlrow olleH'. Я рекомендую вернуться назад и посмотреть, как эти шаги применяются к функции Фибоначчи, а затем попробовать применить их на других примерах (в интернете можно найти много упражнений).

Упорядочивание данных

Этот шаг является ключевым для решения проблем рекурсивным способом, и все же его часто упускают из виду или выполняют неявно. Какие бы данные мы ни использовали, будь то числа, строки, списки, бинарные древа или люди, необходимо явно найти целесообразный порядок, который даст нам видение, как упростить задачу. Порядок полностью зависит от конкретной задачи, но для начала стоит подумать об очевидных вариантах. Например: числа можно упорядочить по величине, строки и списки можно упорядочить по длине, бинарные древа по глубине, а люди могут быть упорядочены бесконечным количеством разумных способов: рост, вес или должность в организации. Это упорядочивание должно соответствовать степени сложности задачи, которую мы пытаемся решить.

По порядку рассчитайсь, йехуу! 

После того, как мы упорядочили данные, нам нужно подумать об этом, как о чём-то, что мы можем сократить. На самом деле, мы можем записать наш порядок в виде последовательности:

0, 1, 2, …, n для чисел (т.е. для int данных d, степень(d) = d)

[], [■], [■, ■], …, [■, … , ■] для списков (len = 0, len = 1, …, len = n и т.д. для списка d, степень(d) = len(d))

Двигаясь справа налево, мы идём от общего («большая часть задачи») случая, к базовым («маленьким частям») случаям. В нашем примере с функцией reverse мы работаем со строкой, и можем взять длину строки за основу, для упорядочивания или определения степени сложности задачи.

Решаем малую часть проблемы

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

Обычно, можно найти очевидное решение: в случае reverse(s), как только мы дойдём до len(s) == 0, имея при этом reverse(''), это будет знаком, что мы нашли ответ, потому что реверс пустой строки ничего не даст, т.е. нам вернётся пустая строка, так как у нас нет символов, которые можно перемещать. Если мы знаем решение для базового случая, и мы знаем порядок, то для нас, степень сложности решения общего случая, уменьшается в зависимости от степени сложности данных, которыми мы оперируем, приближаясь к базовым случаям. Мы должны быть внимательны, чтобы не пропустить ни одного базового случая: они и называются базовыми, потому что образуют основу порядка. Пропуск маленького шага считается распространённой ошибкой в сложных рекурсивных задачах, и приводит к бессмысленным данным или ошибкам.

Переходим к общим случаям

На этом этапе мы обрабатываем данные двигаясь вправо, то есть в сторону высокой степени. Как правило, мы рассматриваем данные произвольной степени, и ищем способ решения проблемы, упрощая её до выражения, представляющего ту же проблему, но в меньшей степени. Например, в случае с числами Фибоначчи мы начали с произвольного значения n и упростили fib(n) до fib(n-1) + fib(n-2), что является выражением, содержащим два экземпляра той же задачи, но в меньшей степени (n-1 и n-2, соответственно).

Большой случай?

Возвращаясь к алгоритму reverse, мы можем рассмотреть произвольную строку с длинной n, и предположить, что наша reverseфункция работает для всех строк с длинной меньше n. Как мы можем использовать это, решая задачу для строки с длинной n? Мы могли бы сделать реверс строки, переместив всё, кроме последнего символа, а затем вставить этот последний символ в начало. В коде:

reverse(string) = reverse(string[-1]) + reverse(string[:-1])

где string[-1] соответствует последнему символу, а string[:-1]соответствует строке без последнего символа (это питонизм). Последний член функции reverse(string[:-1]), и является нашей исходной задачей, но он оперирует со строкой длины n-1. Таким образом, мы выразили нашу исходную задачу в решении той же задачи, но в уменьшенной степени.

Применив это решение к функции reverse, мы получаем следующее:

reverse(string):
  if len(string) == 0:
    return ''
  else:
    return string[-1] + reverse(string[:-1])
Визуализации рекурсивной функции reverse

Часто бывает так, что нам нужно рассмотреть несколько рекурсивных случаев, так как данные определённого типа, могут принимать разные формы, но это полностью зависит от задачи. Например, если мы хотим сгладить список элементов, некоторые из которых сами могут быть списками, нам нужно будет различать случаи, когда элемент, который мы вытаскиваем из списка, является отдельным элементом или подсписком, что приводит по крайней мере к двум рекурсивным случаям.

Напутствие

Единственный способ улучшить свои навыки в рекурсии — это практика. В интернете можно найти тысяч примеров задач, подходящих для рекурсивного решения — испытайте себя. Однажды, вы неизбежно научитесь рекурсии, но, если у вас возникнут трудности с рекурсивным решением проблемы, попробуйте вместо этого итерацию. Рекурсия поможет вам решать проблемы не только в программировании, но и в повседневной жизни. Если проблема не подходит для рекурсии, что ж, такое бывает; со временем вы научитесь чувствовать, где следует использовать рекурсивный подход, а где итеративный.

Иногда в более сложных рекурсивных задачах, шаги 2 и 3, о которых мы говорили, принимают форму более циклического процесса. Если вы не можете быстро найти общее решение проблемы, попробуйте решить рекурсивные (большие) случаи и базовые (маленькие) случаи, которые сможете найти, а затем посмотрите, как в результате разделились разные части данных. Это должно выявить любые недостающие базовые и рекурсивные случаи или те, которые плохо взаимодействуют друг с другом и нуждаются в переосмыслении.

Наконец, помните, что выявление порядка является самым важным шагом к решению рекурсивной задачи, и ваша цель рассмотреть как правый (рекурсивный), так и левый (базовый) случаи этого порядка, чтобы решить задачу для всех данных определённого типа.

На этом всё, спасибо за внимание.

Перевод статьи Tom Grigg: Recursive Programming

Рекурсия — это… Что такое Рекурсия?

Рекурсивное изображение экрана Визуальная форма рекурсии страницы Википедии

Реку́рсия — процесс повторения элементов самоподобным образом. Например, если два зеркала установить друг напротив друга, то возникающие в них вложенные отражения суть одна из форм бесконечной рекурсии.

Термин «рекурсия» используется в различных специальных областях знаний — от лингвистики до логики, но наиболее широкое применение находит в математике и информатике. В математике и информатике рекурсия имеет отношение к методу определения функций: рекурсивно заданная функция в своём определении содержит себя, в частности, рекурсивной является функция, заданная рекуррентной формулой. Таким образом, можно одним выражением дать бесконечный набор способов вычисления функции, определить множество объектов через самого себя с использованием ранее заданных частных определений.

С рекурсией тесно связана математическая индукция: она является естественным способом доказательства свойств функций на натуральных числах, рекурсивно заданных через свои меньшие значения.

В математике

В программировании

Функции

В программировании рекурсия — вызов функции (процедуры) из неё же самой, непосредственно (простая рекурсия) или через другие функции (сложная или косвенная рекурсия), например, функция вызывает функцию , а функция  — функцию . Количество вложенных вызовов функции или процедуры называется глубиной рекурсии.

Преимущество рекурсивного определения объекта заключается в том, что такое конечное определение теоретически способно описывать бесконечно большое число объектов. С помощью рекурсивной программы же возможно описать бесконечное вычисление, причём без явных повторений частей программы.

Реализация рекурсивных вызовов функций в практически применяемых языках и средах программирования, как правило, опирается на механизм стека вызовов — адрес возврата и локальные переменные функции записываются в стек, благодаря чему каждый следующий рекурсивный вызов этой функции пользуется своим набором локальных переменных и за счёт этого работает корректно. Оборотной стороной этого довольно простого по структуре механизма является то, что на каждый рекурсивный вызов требуется некоторое количество оперативной памяти компьютера, и при чрезмерно большой глубине рекурсии может наступить переполнение стека вызовов. Вследствие этого, обычно рекомендуется избегать рекурсивных программ, которые приводят (или в некоторых условиях могут приводить) к слишком большой глубине рекурсии.

Имеется специальный тип рекурсии, называемый «хвостовой рекурсией». Интерпретаторы и компиляторы функциональных языков программирования, поддерживающие оптимизацию кода (исходного или исполняемого), автоматически преобразуют хвостовую рекурсию к итерации, благодаря чему обеспечивается выполнение алгоритмов с хвостовой рекурсией в ограниченном объёме памяти. Такие рекурсивные вычисления, даже если они формально бесконечны (например, когда с помощью рекурсии организуется работа командного интерпретатора, принимающего команды пользователя), никогда не приводят к исчерпанию памяти. Однако, далеко не всегда стандарты языков программирования чётко определяют, каким именно условиям должна удовлетворять рекурсивная функция, чтобы транслятор гарантированно преобразовал её в итерацию. Одно из редких исключений — язык Scheme (диалект языка Lisp), описание которого содержит все необходимые сведения.

Любую рекурсивную функцию можно заменить циклом и стеком.

Данные

Описание типа данных может содержать ссылку на саму себя. Подобные структуры используются при описании списков и графов. Пример описания списка (C++):

 struct element_of_list
 {
   element_of_list *next; /* ссылка на следующий элемент того же типа */
   int data; /* некие данные */
 };

Рекурсивная структура данных зачастую обуславливает применение рекурсии для обработки этих данных.

В физике

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

Другим примером бесконечной рекурсии является эффект самовозбуждения (положительной обратной связи) у электронных схем усиления, когда сигнал с выхода попадает на вход, усиливается, снова попадает на вход схемы и снова усиливается. Усилители, для которых такой режим работы является штатным, называются автогенераторы.

В лингвистике

См. также: Рекурсия (лингвистика)

Способность языка порождать вложенные предложения и конструкции. Базовое предложение «кошка съела мышь» может быть за счёт рекурсии расширено как Ваня догадался, что кошка съела мышь, далее как Катя знает, что Ваня догадался, что кошка съела мышь и так далее. Рекурсия считается одной из лингвистических универсалий, то есть свойственна любому естественному языку. Однако, в последнее время активно обсуждается возможное отсутствие рекурсии в одном из языков Амазонии — пираха, которое отмечает лингвист Дэниэл Эверетт (англ.)[1].

В культуре

Большая часть шуток о рекурсии касается бесконечной рекурсии, в которой нет условия выхода, например, известно высказывание: «чтобы понять рекурсию, нужно сначала понять рекурсию».

Весьма популярна шутка о рекурсии, напоминающая словарную статью:

Несколько рассказов Станислава Лема посвящены (возможным) казусам при бесконечной рекурсии:

  • рассказ про Йона Тихого «Путешествие четырнадцатое» из «Звёздных дневников Ийона Тихого», в котором герой последовательно переходит от статьи о сепульках к статье о сепуляции, оттуда к статье о сепулькариях, в которой снова стоит отсылка к статье «сепульки»:

Нашёл следующие краткие сведения:
«СЕПУЛЬКИ — важный элемент цивилизации ардритов (см.) с планеты Энтеропия (см.). См. СЕПУЛЬКАРИИ».
Я последовал этому совету и прочёл:
«СЕПУЛЬКАРИИ — устройства для сепуления (см.)».
Я поискал «Сепуление»; там значилось:
«СЕПУЛЕНИЕ — занятие ардритов (см.) с планеты Энтеропия (см.). См. СЕПУЛЬКИ».

Лем С. «Звёздные дневники Ийона Тихого. Путешествие четырнадцатое.»

  • Рассказ из «Кибериады» о разумной машине, которая обладала достаточным умом и ленью, чтобы для решения поставленной задачи построить себе подобную, и поручить решение ей (итогом стала бесконечная рекурсия, когда каждая новая машина строила себе подобную и передавала задание ей).
  • Рекурсивные акронимы: GNU (GNU Not Unix), PHP (PHP: Hypertext Preprocessor) и т. д.

См. также

Примечания

Что такое рекурсия и как ее использовать?

Рекурсия – это забавная концепция программирования, но может быть немного сложной для изучения. Рекурсия просто означает что-то, что повторяется. Если вы хотите увидеть нахальный пример рекурсии, попробуйте поискать рекурсию в Google. Вы найдете пасхальное яйцо, в котором предложения результатов поиска рекурсивны. С другой стороны, если вы хотите научиться кодировать рекурсивную функцию, читайте дальше!

Что такое рекурсивная функция?

Рекурсивная функция – это функция, которая вызывает сама себя. По сути, вы создаете цикл с функцией. Как вы понимаете, написать эти функции может быть непросто. Вы не хотите, чтобы ваш код работал вечно.

Подобно циклу, рекурсивная функция будет управляться условием. Как только условие выполнено, функция перестает вызывать саму себя, что останавливает цикл. Вот как вы можете создать функцию, которая вызывает сама себя, не выполняя ее вечно.

Хотя рекурсивная функция действует как цикл, компьютер выполняет ее иначе. Итак, некоторые алгоритмы более эффективны в цикле, а другие выигрывают от рекурсивной функции. Но прежде чем мы рассмотрим, как использовать рекурсивную функцию, вам нужно знать, как ее написать.

Как написать рекурсивную функцию

Все рекурсивные функции имеют одинаковую базовую структуру:

 FUNCTION name
IF condition THEN
RETURN result
ELSE
CALL FUNCTION name
END FUNCTION

Приведенный выше пример написан в псевдокоде. Он описывает структуру функции, которая может быть применена к любому языку. Для простоты в этой статье мы сконцентрируемся на Python.

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

Если условие не выполняется, функция вызовет себя. Итак, если вы хотите отправить информацию в следующий цикл, вам нужно будет отправить ее как аргумент в вашей функции. Это может дать рекурсивным функциям гораздо больше возможностей.

Связанный: Что такое функция в программировании?

Пример рекурсивной функции в Python

Будет намного легче понять, как работает рекурсия, когда вы увидите ее в действии. Чтобы продемонстрировать это, давайте напишем рекурсивную функцию, которая возвращает факториал числа.

Факториалы возвращают произведение числа и всех целых чисел перед ним. Например, факториал 5 равен 5 x 4 x 3 x 2 x 1 или 120.

 def factorialFunction(numberToMultiply):
if numberToMultiply == 1 :
return 1
else :
return numberToMultiply * factorialFunction(numberToMultiply - 1)

result = factorialFunction(3)
print(result)
//Outputs: 6

Вышеупомянутая программа выдаст вам результат 6, который является факториалом числа 3. Поначалу это может немного сбивать с толку. Поможет, если мы пройдемся по программе шаг за шагом.

  1. Когда функция вызывается, numberToMultiply равно 3.
  2. Условие не выполняется, поэтому переходим к условию else .
  3. Наша функция возвращает 3 *, но затем останавливается. Он должен вызвать себя, чтобы определить остальную часть возвращаемого значения.
  4. Когда на этот раз вызывается функция, значение numberToMultiply равно 2.
  5. Условие не выполняется, поэтому переходим к условию else.
  6. Наша функция возвращает 2 *, но затем останавливается. Он должен вызвать себя, чтобы определить остальную часть возвращаемого значения.
  7. Функция вызывается снова. На этот раз значение numberToMultiply равно 1.
  8. Наше условие if выполнено. Функция возвращает 1.
  9. Функция из шага 6 теперь может возвращать 2 * 1 функции из шага 3.
  10. Функция на третьем шаге теперь может возвращать 3 * 2 * 1, что равно 6.

Рекурсия – сложная концепция. Может быть полезно думать об этом как о наложении одной функции поверх другой. Как только одна функция будет окончательно разрешена, она может отправить информацию обратно в стек, пока все функции не получат свой ответ.

На самом деле это в значительной степени то, что делает ваш компьютер. Когда вы вызываете функцию, она сохраняется в памяти до тех пор, пока не будет возвращена. Это означает, что рекурсивные функции могут использовать гораздо больше памяти, чем цикл.

Итак, писать циклы как рекурсивные функции может быть неэффективно, но это отличный способ попрактиковаться в их построении. Вы должны иметь возможность кодировать циклы как рекурсивные функции с аналогичными результатами.

Пример преобразования цикла в рекурсивную функцию

 print("Enter an even number:")
i = int(input())
while (i % 2) != 0 :
print("That number is not even. Please enter a new number:")
i = int(input())

Этот цикл также можно записать рекурсивно как:

 def recursiveFunction(number) :
if (number % 2) == 0 :
return number
else:
print("That number is not even. Please enter a new number:")
recursiveFunction(int(input()))

print("Enter and even number:")
i = recursiveFunction(int(input()))

Первый шаг – определить, когда вы хотите, чтобы ваша функция остановилась. В этом случае мы хотим, чтобы он останавливался после ввода четного числа. В нашем примере число отслеживает ввод пользователя. Если они вводят четное число, мы возвращаем число. В противном случае мы продолжим запрашивать новый номер.

Чтобы настроить цикл, мы снова вызываем нашу функцию. Но на этот раз число, которое мы передаем следующей функции, – это новый номер, введенный пользователем. Следующий вызов функции проверит номер.

Это действительно плохая функция! Да, он проверяет, четное ли число, как и наш цикл, но неэффективно. Каждый раз, когда пользователь вводит нечетное число, функция сохраняется в памяти и вызывается новая функция. Если вы сделаете это достаточно много раз, у вас закончится память!

Связанный: Основные примеры Python, которые помогут вам быстро изучить

Реальный пример рекурсивной функции

Приведенные выше примеры были хорошими примерами того, когда не использовать рекурсию. Итак, где используется рекурсия? Хороший пример использования рекурсии – поиск в двоичном дереве.

Когда данные структурированы в виде двоичного дерева, вам придется пройти множество путей для поиска данных. В каждой точке дерева вы должны решить, хотите ли вы продолжить поиск справа или слева. Вы можете сохранить в переменной, какую часть дерева вы посетили, но рекурсивная функция, естественно, может отслеживать эту информацию.

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

 FUNCTION searchTree(branchToSearch)
IF find 6 OR end of tree THEN
RETURN result
ELSE
PROCESS branch
CALL FUNCTION searchTree(left)
CALL FUNCTION searchTree(right)
END FUNCTION

В этом примере псевдокода алгоритм сначала будет искать в левой части дерева. Каждый раз, когда он посещает новый номер, функция приостанавливается и сохраняется в памяти. Это позволяет нам отслеживать, где мы были.

Алгоритм всегда будет сначала искать слева, насколько это возможно. как только он достигнет конца дерева, searchTree (слева) завершится и проверит правую сторону. Как только обе стороны проверены, поиск дублирует одну ветвь и продолжает проверку правой стороны.

Если бы алгоритмы просматривали все дерево, они бы делали это в следующем порядке:

2, 7, 2, 6, 5, 11, 5, 9 и 4

Посмотрите, сможете ли вы продолжить, используя приведенный выше псевдокод.

Обзор рекурсии

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

При написании рекурсивной функции начните с решения, как вы хотите выйти из функции. Затем определите, как настроить цикл. Определите, какую информацию нужно отправить при следующем вызове функции, а что нужно вернуть.

Лучший способ научиться рекурсии – это практиковать ее и учиться на своих ошибках. Посмотрите на свой старый код и поставьте перед собой задачу переписать циклы как рекурсивные функции. Скорее всего, это не сделает ваш код более эффективным, но это будет хорошей практикой.

Связанный

Как работает Рекурсия в Python — пример рекурсивной функции

Рекурсию не очень просто понять при первом знакомстве, но без ее понимания в разработке будет тяжело. В этом материале рассмотрим:

  • Рекурсивную функцию поиска факториала.
  • Как рекурсивные функции работают в коде.
  • Действительно ли рекурсивные функции выполняют свои задачи лучше итеративных?

Рекурсивные функции

Рекурсивная функция — это та, которая вызывает сама себя.

В качестве простейшего примера рассмотрите следующий код:


def factorial_recursive(n):
if n == 1:
return n
else:
return n*factorial_recursive(n-1)

Вызывая рекурсивную функцию здесь и передавая ей целое число, вы получаете факториал этого числа (n!).

Вкратце о факториалах

Факториал числа — это число, умноженное на каждое предыдущее число вплоть до 1.

Например, факториал числа 7:
7! = 7*6*5*4*3*2*1 = 5040

Вывести факториал числа можно с помощью функции:


num = 3
print(f"Факториал {num} это {factorial_recursive(num)}")

Эта функция выведет: «Факториал 3 это 6». Еще раз рассмотрим эту рекурсивную функцию:

def factorial_recursive(n):

    ...

По аналогии с обычной функцией имя рекурсивной указывается после def, а в скобках обозначается параметр n:

def factorial_recursive(n):
    if n == 1:
        return n
    else:
        return n*factorial_recursive(n-1)

Благодаря условной конструкции переменная n вернется только в том случае, если ее значение будет равно 1. Это еще называют условием завершения. Рекурсия останавливается в момент удовлетворения условиям.

def factorial_recursive(n):
    if n == 1:
        return n
    else:
        return n*factorial_recursive(n-1)

В коде выше выделен фрагмент самой рекурсии. В блоке else условной конструкции возвращается произведение n и значения этой же функции с параметром n-1.

Это и есть рекурсия. В нашем примере это так сработало:

3 * (3-1) * ((3-1)-1)  # так как 3-1-1 равно 1, рекурсия остановилась

Детали работы рекурсивной функции

Чтобы еще лучше понять, как это работает, разобьем на этапы процесс выполнения функции с параметром 3.

Для этого ниже представим каждый экземпляр с реальными числами. Это поможет «отследить», что происходит при вызове одной функции со значением 3 в качестве аргумента:


# Первый вызов
factorial_recursive(3):
if 3 == 1:
return 3
else:
return 3*factorial_recursive(3-1)

# Второй вызов
factorial_recursive(2):
if 2 == 1:
return 2
else:
return 2*factorial_recursive(2-1)

# Третий вызов
factorial_recursive(1):
if 1 == 1:
return 1
else:
return 1*factorial_recursive(1-1)

Рекурсивная функция не знает ответа для выражения 3*factorial_recursive(3–1), поэтому она добавляет в стек еще один вызов.

Как работает рекурсия

/\ factorial_recursive(1) - последний вызов
|| factorial_recursive(2) - второй вызов
|| factorial_recursive(3) - первый вызов

Выше показывается, как генерируется стек. Это происходит благодаря процессу LIFO (last in, first out, «последним пришел — первым ушел»). Как вы помните, первые вызовы функции не знают ответа, поэтому они добавляются в стек.

Но как только в стек добавляется вызов factorial_recursive(1), для которого ответ имеется, стек начинает «разворачиваться» в обратном порядке, выполняя все вычисления с реальными значениями. В процессе каждый из слоев выпадает в процессе.

  • factorial_recursive(1) завершается, отправляет 1 в
  • factorial_recursive(2) и выпадает из стека.
  • factorial_recursive(2) завершается, отправляет 2*1 в
  • factorial_recursive(3) и выпадает из стека. Наконец, инструкция else здесь завершается, возвращается 3 * 2 = 6, и из стека выпадает последний слой.

Рекурсия в Python имеет ограничение в 3000 слоев.


>>> import sys
>>> sys.getrecursionlimit()
3000

Рекурсивно или итеративно?

Каковы же преимущества рекурсивных функций? Можно ли с помощью итеративных получить тот же результат? Когда лучше использовать одни, а когда — другие?

Важно учитывать временную и пространственную сложности. Рекурсивные функции занимают больше места в памяти по сравнению с итеративными из-за постоянного добавления новых слоев в стек в памяти. Однако их производительность куда выше.

Рекурсия может быть медленной, если реализована неправильно

Тем не менее рекурсия может быть медленной, если ее неправильно реализовать. Из-за этого вычисления будут происходить чаще, чем требуется.

Написание итеративных функций зачастую требуется большего количества кода. Например, дальше пример функции для вычисления факториала, но с итеративным подходом. Выглядит не так изящно, не правда ли?


def factorial_iterative(num):
factorial = 1
if num < 0:
print("Факториал не вычисляется для отрицательных чисел")
else:
for i in range (1, num + 1):
factorial = factorial*i
print(f"Факториал {num} это {factorial}")

О пользе рекурсии

О пользе рекурсии

Эту заметку о пользе рекурсии я написал после прочтения соответствующей части книги С. Макконнелла «Совершенный код». Книга прекрасная, но, на мой взгляд, автор совершенно напрасно обещает уволить сотрудника, использующего рекурсию. Мне рекурсия помогала много раз, и я видел множество превосходных примеров её использования.

В заметке я буду рассматривать рекурсию на классическом примере — вычисление факториала. На более сложных зачах эффект от использования рекурсии (как положительный, так и отрицательный) может оказаться на много больше.

Компактность записи

Итак, давайте сравним записи функций, вычисляющих факториал с использованием рекурсии и без использования рекурсии. Оказывается, слухи о громоздкости рекурсии во многом преувеличены.

Небольшое замечание: для краткости, все мои реализации (и рекурсивные и не рекурсивные) будут достаточно просты. Например, я не буду проверять корректность входных данных (отрицательное число, вообще не число). Вопросов надёжности кода я коснусь чуть ниже.

# пример 1
# вычисление факториала на языке Python без рекурсии
def fac(n):
    f = 1
    i = 2
    while i <= n:
        f *= i
        i += 1
    return f

Многие могут сказать, что функция чрезмерно усложнена добавлением переменной i. Чуть ниже, я поясню, зачем я это сделал, а пока приведу классический вариант:

# пример 2
# Python; без рекурсии; классика
def fac(n):
    f = 1
    while n > 1:
        f *= n
        n -= 1
    return f

У такого подхода есть один важный недостаток, к нему мы скоро вернёмся. А пока давайте посмотрим на рекурсивные реализации.

Сперва классическая реализация с рекурсией, всё на том же Python:

# пример 3
# Python; с рекурсией; классика
def fac(n):
    if n == 0:
        return 1
    else:
        return n * fac(n-1)

Обратите внимание, на сколько близко эта запись перекликается с математическим определение факториала.

Можно сэкономить одну строчку:

# пример 4 (экономичная запись примера 3)
# Python; с рекурсией; классика
def fac(n):
    if n == 0:
         return 1
    return n * fac(n-1)

Ту же самую мысль можно записать ещё компактней

# пример 5 (одно-строчная запись примера 3)
def fac(n): return (1 if n == 0 else n * fac(n-1))

Этот пример работает только в Python 2.5 и старше.

Приведу два примера на Haskell:

-- пример 7
-- запись примера 3 на Haskell
fac n = if n == 0
          then 1
          else n * fac (n-1)

Приведу ещё один, более компактный, но вполне понятный для неподготовленного читателя:

-- пример 8
-- реализация рекурсивного вычисления факториала
-- на Haskell; дополнительно компактности удалось
-- достичь за счёт использования клозов (от clause)
fac 0 = 1
fac n = n * fac (n-1)

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

На мой взгляд, дело обстоит противоположным образом: в тех случаях, где рекурсия оправдана, она позволяет значительно сократить объём кода и сделать его на много понятней.

Как же можно повысить понятность кода, используя рекурсию?

Неизменяемость переменных

При программировании бывает полезно придерживаться концепции неизменяемости переменных (многие языки программирования вообще не допускают изменения переменных). Это позволяет убить сразу много зайцев:

  • во-первых, вы избавляетесь от сайд-эффектов (side effect) — побочных эффектов, связанных с тем, что одна и та же переменная принимает разные значения в разные моменты времени;
  • во-вторых, вы можете легко проверять данные на корректность; это достаточно делать один раз и все проверки можно группировать, скажем, в начале функции; это повышает не только надёжность кода, но и его читабельность, а так же, позволяет ничего не забыть;
  • в-третьих, вы существенно повышаете читабельность кода, так как читающему не надо просматривать весь код, чтобы отследить эволюцию переменной; ему достаточно найти то место, где переменной присвоено значение, а дальше он может быть уверен, что это значение не изменится.

Давайте рассмотрим эти аспекты подробней.

Избавление от сайд-эффектов (side effect)

Рассмотрим рекурсивную и не рекурсивную реализацию. Повторю их здесь.

Не рекурсивная (одна из, она мне нравится больше; почему — поясню ниже)

# пример 1
# вычисление факториала на языке Python без рекурсии
def fac(n):
    f = 1
    i = 2
    while i <= n:
        f *= i
        i += 1
    return f

Тут мы видим сразу две изменяемые переменные — f и i. Причём i оказывает влияние на f в одном месте, а изменяет своё значение — в другом. Это потенциальный источник ошибок такого вида:

# пример 1 с ошибкой
def fac(n):
    f = 1
    i = 2
    while i <= n:
        i += 1 # Ошибка
        f *= i # Порядок выполнения операций не верный
    return f

Даже в таком тривиальном коде заметить ошибку не легко. С увеличением объёма кода, находить ошибки, связанные с побочными эффектам, становится очень сложно.

Самое неприятное в таких ошибках то, что компилятор или интерпретатор, в большинстве случаев, ничего не заподозрит; с его точки зрения, код абсолютно правильный. Чтобы найти такую ошибку, вам придётся кропотливо вычитывать весь код (или не менее кропотливо работать в отладчике, или читать километровые файлы детальных протоколов, одно другого не слаще), следя за всеми изменениями переменных, отслеживая множество вариантов развития событий, учитывая возможную много-поточность выполнения операций… Весь этот ад появляется только потому, что переменные в нашей программе изменяемые и одно действие наводит побочный эффект на другое действие.

Вариант с рекурсией полностью избавлен от этого недостатка (приведу его здесь снова):

# пример 3
# Python; с рекурсией; классика
def fac(n):
    if n == 0:
        return 1
    else:
        return n * fac(n-1)

В процессе выполнения функции fac ни одна переменная не изменяется. Это обстоятельство может сильно упростить чтение и понимание кода.

Неизменяемость переменных даёт ещё одно ценное преимущество: у каждой переменной появляется вполне определённое назначение, которое не может быть изменено.

Лёгкость проверки корректности значений

Так как значения не изменяются, их можно легко проверять на корректность. Причём все проверки можно группировать, не опасаясь, что переменная изменится к моменту, когда над ней будут производиться какие-то действия.

Строго говоря, проверка становится вполне естественной веткой в существующем алгоритме. Вот модифицированный пример 3:

# пример 3 с проверкой значений на "не-отрицательность"
def fac(n):
    if n == 0:
        return 1
    if n >  0:
        return n * fac(n-1)
    else:
        return 'ERROR'

Чтобы реализовать аналогичную проверку в не рекурсивном варианте кода (примеры 1 и 2), пришлось бы добавить отдельный проверяющий механизм. И это не случайно, причины кроются в различном подходе к работе с данными. К этим различиям я ещё вернусь в секции «»Данные, управляемые программами» против «программ, управляемых данными»».

Однозначность назначения каждой переменной

Действительно, если переменные сохраняют свои значения, то и их назначение остаётся строго неизменным. В сочетании с удачными именами это обстоятельство может оказать неоценимую помощь при чтении и отладке кода.

Взгляните ещё раз на рекурсивный пример 3: переменная n сохраняет единственное назначение.

Чтобы идея была понятней, давайте введём ещё одну переменную (конечно же, она тоже будет неизменяемой):

# пример 3 с дополнительно переменной
def fac(n):
    if n == 0:
        f = 1
    else:
        f = n * fac(n-1)
    return f

Теперь переменных две и их смысл одинаков везде, где они используются: n — аргумент, f — факториал n (и ни что иное).

Теперь пришло время объяснить, почему мне так не симпатичен пример 2 (приведу его здесь снова):

# пример 2
# Python; без рекурсии; классика
def fac(n):
    f = 1        # первое использование f
    while n > 1:
        f *= n   # второе использование f
        n -= 1
    return f     # третье использование f

Здесь переменная f используется трижды, и все три раза она имеет разный смысл:

  • первый раз — начальное значение — фиксированная константа;
  • второй раз она используется как аккумулятор для хранения промежуточных результатов;
  • трети раз — это искомое значение — факториал n.

Этот код — прекрасный образец того, как можно максимально эффективно запутывать программу, используя одну и ту же переменную в разных качествах.

Конечно, в данном случае, прочитать программу не сложно, но если она будет решать более сложную задачу, содержать тысячи строк, а переменная f будет не одна и будет не скаляром… Понять замысел программиста станет очень сложно.

И снова, источник всех бед только то, что переменная f — изменяемая.

«Данные, управляемые программами» против «программ, управляемых данными»

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

Первый — «программа управляет данными». Это наиболее простой и общеизвестный способ взаимодействия с данными. Если данные просты, то он позволяет без труда обрабатывать их, но если данные сложны (например, это некие конструкции, допускающие многократные вложения: HTML, XML, PostScript или просто программа на некотором языке высокого уровня), то алгоритму приходится обрабатывать множество возможных вариантов. Одна из наибольших проблем — обработка ошибок. Чтобы точно диагностировать ошибку, приходится рассматривать множество вариантов во множестве мест кода. Группировка проверок может значительно помочь программисту, но такой подход таит потенциальную опасность того, что значение изменится где-то между проверкой его корректности и его использованием.

Создавая такой код, очень легко что-то упустить и создать «дырку» — такой код, который будет работать непредусмотренным образом, если получит непредусмотренные автором данные. То есть злоумышленник сможет скомбинировать такие входные данные, которые заставят код работать не так, как задумывал автор.

Второй подход — «данные управляют программой». Этот подход используется в функциональных языках программирования и наиболее чисто реализован (на мой взгляд) в XSLT.

При написании кода в этом стиле, вы не создаёте алгоритм, вы не описываете последовательность действий. Вы пишете набор «формул», которые потом будут применяться к входным данным для получения результата. В момент написания вы не знаете в каком порядке будут выполняться инструкции, которые вы кодируете; потому, что вы не знаете, какие данные будет обрабатывать ваша программа. Но благодаря тому, что все ваши переменные являются неизменяемыми, вы можете не волноваться о порядке выполнения команд.

Давайте я приведу чуть-модифицированный вариант третьего примера:

# пример 3 (чуть модифицированный)
def fac(n):
    if n == 0: return 1
    if n != 0: return n * fac(n-1)

Такая запись делает более очевидным тот факт, что функция fac не кодирует никакого алгоритма; она не определяет последовательность действий. В ней записано два утверждения:

если n равно нулю, то результат -- 1
если n не равно нуля, то результат -- выражение

Эти строки можно выполнять в любом порядке. Для программиста не важно в каком порядке они будут отрабатываться. Он может отладить каждую ветку отдельно, а потом объединить их, не опасаясь сайд-эффектов. То, какая именно ветка будет работать, определятся входными данными. Поэтому подход и называется «данные управляют программой».

Подход, когда данные управляют программой даёт множество преимуществ, основными из которых являются: лёгкость понимания кода и простота написания обработчиков ложных данных, независимость одних частей кода от других. Но главное, такой подход не позволяет программисту создавать «дырки».

Рекурсия расточительна

«More computing sins are committed in the name of efficiency (without necessarily achieving it) than for any other single reason — including blind stupidity.»
— W. A. Wulf
«We should forget about small efficiencies, say about 97% of the time: premature optimization is the root of all evil.»
— C. A. R. Hoare

Это правда. Очень существенным недостатком рекурсии, является её расточительность.

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

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

С другой стороны, алгоритм архивирования вряд ли изменится, и если он написан хорошо, то его доработка и развитие не понадобится. Этого нельзя сказать об интерфейсе, здесь совершенству нет предела. В таком случае, код, описывающий интерфейс, должен быть понятным, простым и легко наращиваться.

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

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

Кроме того, не надо забывать про хвостовую рекурсию. Нашу рекурсивную процедуру вычисления факториала можно записать так:

def fac(n, a=None):
    if a is None:
        a = 1
    if n < 2:
        return a
    return fac(n - 1, a * n)

Мы мало что изменили. Фактически, мы просто поменяли порядок умножения. Но теперь мы получили вычисление факториала с хвостовой рекурсией.

Она характерна тем, что после рекурсивного вызова не выполняется никаких действий (наш предыдущий вариант таким свойством не обладал). В этом случае компилятор может превратить рекурсию в цикл. В gcc это сделает уже -O2-оптимизация. То есть, мы получили рекурсию без дополнительных накладных расходов.

Конечно, далеко не всегда удаётся переформулировать рекурсию в виде концевой.

Рекурсия позволяет создавать код с неизменяемыми переменными, что

  • делает код более читабельным,
  • защищает от ошибок типа «действия выполнены в не верном порядке», «использована не-инициализированная переменная» и других аналогичных,
  • облегчает организацию контроля корректности входных данных,
  • позволяет читать код с любого места, не просматривая его весь, отслеживая все изменения переменной,
  • облегчает отладку.

В некоторых случаях, рекурсия позволяет более ясно сформулировать идею алгоритма; например, это относится к алгоритму быстрой сортировки — quicksort — который рекурсивен по своей природе.

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

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

В любом случае, существует множество языков, в которых рекурсия — единственное средство, для выполнения многих действий. К таким языкам относятся не только «экзотические» функциональные языки, такие как Haskell, но и средства более широкого применения: XSLT-процессоры, макро-процессор m4 (основа системы autoconf и многих систем конфигурирования), и другие средства. Такое «тяготение» к рекурсии — не следствие ограниченности этих языков; напротив, эти языки специально оптимизированы для использования рекурсии; они активно эксплуатируют факт неизменяемости переменных и способны выполнить множество оптимизаций, избавляя программиста от многих забот.




Отправить

Когда использовать рекурсию?

От того, кто практически живет в рекурсии, я постараюсь пролить свет на эту тему.

Когда вы впервые знакомитесь с рекурсией, вы узнаете, что это функция, которая вызывает себя и в основном демонстрируется с помощью таких алгоритмов, как обход дерева. Позже вы обнаружите, что он широко используется в функциональном программировании для таких языков, как LISP и F #. С F # я пишу, большинство из того, что я пишу, является рекурсивным и сопоставлением с образцом.

Если вы узнаете больше о функциональном программировании, таком как F #, вы узнаете, что списки F # реализованы в виде односвязных списков, что означает, что операции, которые обращаются только к заголовку списка, являются O (1), а доступ к элементу — O (n). Когда вы узнаете это, вы стремитесь просмотреть данные в виде списка, создавая новый список в обратном порядке, а затем переворачивая список, прежде чем вернуться из функции, которая очень эффективна.

Теперь, если вы начнете думать об этом, вы скоро поймете, что рекурсивные функции будут выдвигать кадр стека каждый раз, когда выполняется вызов функции, и могут вызвать переполнение стека. Однако, если вы создаете свою рекурсивную функцию, чтобы она могла выполнять хвостовой вызов, а компилятор поддерживает возможность оптимизировать код для хвостового вызова. т.е. .NET OpCodes.Tailcall Field вы не будете вызывать переполнение стека. С этого момента вы начинаете писать любой цикл как рекурсивную функцию, а любое решение — как совпадение; дни ifи whileтеперь история.

Как только вы переходите на ИИ, используя возврат на таких языках, как PROLOG, все становится рекурсивным. Хотя для этого нужно думать совершенно иначе, чем просто для императивного кода, если PROLOG является подходящим инструментом для решения проблемы, он освобождает вас от необходимости писать много строк кода и может значительно сократить количество ошибок. Смотрите: Amzi клиент eoTek

Вернемся к вашему вопросу о том, когда использовать рекурсию; Я смотрю на программирование одним способом: на одном конце — аппаратное обеспечение, а на другом — абстрактные концепции. Чем ближе к проблеме аппаратного обеспечения, тем больше я думаю о императивных языках ifи whileчем более абстрактно эта проблема, тем больше я думаю о языках высокого уровня с рекурсией. Однако, если вы начнете писать системный код низкого уровня и тому подобное и хотите убедиться, что он действителен, вам пригодятся такие решения, как средства доказательства теорем , которые в значительной степени зависят от рекурсии.

Если вы посмотрите на улицу Джейн, вы увидите, что они используют функциональный язык OCaml . Хотя я не видел ни одного из их кода, прочитав о том, что они упоминают о своем коде, они угрюмо думают рекурсивно.

РЕДАКТИРОВАТЬ

Поскольку вы ищете список применений, я дам вам базовую идею о том, что искать в коде, и список основных применений, которые в основном основаны на концепции катаморфизма, которая выходит за рамки базовых.

Для C ++: если вы определяете структуру или класс, который имеет указатель на ту же структуру или класс, тогда рекурсия должна быть рассмотрена для методов обхода, которые используют указатели.

Простой случай — это односторонний связанный список. Вы должны обработать список, начиная с головы или хвоста, а затем рекурсивно обходить список с помощью указателей.

Дерево — это еще один случай, когда часто используется рекурсия; настолько, что если вы видите обход дерева без рекурсии, вы должны начать спрашивать, почему? Это не так, но то, что следует отметить в комментариях.

Обычное использование рекурсии:

определение. Рекурсия в программировании (примеры)

Рекурсии являются интересными событиями сами по себе, но в программировании они представляют особенную важность в отдельных случаях. Впервые сталкиваясь с ними, довольно значительное количество людей имеют проблемы с их пониманием. Это связано с огромным полем потенциального применения самого термина в зависимости от контекста, в котором «рекурсия» используется. Но можно надеяться, что эта статья поможет избежать возможного недоразумения или непонимания.

Слово «рекурсия» имеет целый спектр значений, которые зависят от области, в которой оно применяется. Универсальное обозначение является таким: рекурсии — это определения, изображения, описания объектов или процессов в самих объектах. Возможны они только в тех случаях, когда объект является частью самого себя. По-своему определяют рекурсию математика, физика, программирование и ряд других научных дисциплин. Практическое применение она нашла в работе информационных систем и физических экспериментах.


Что подразумевают под рекурсией в программировании?

Рекурсивными ситуациями, или рекурсией в программировании, называют моменты, когда процедура или функция программы вызывает саму себя. Как бы странно для тех, кто начал изучать программирование, это ни звучало, здесь нет ничего странного. Следует запомнить, что рекурсии – это не сложно, и в отдельных случаях они заменяют циклы. Если компьютеру правильно задать вызов процедуры или функции, он просто начнёт её выполнять.

Рекурсия может быть конечной или бесконечной. Для того чтобы первая прекратила сама себя вызывать, в ней же должны быть условия прекращения. Это может быть уменьшение значения переменной и при достижении определённого значения остановка вызова и завершение программы/переход к последующему коду, в зависимости от потребностей достичь определённых целей. Под бесконечной рекурсией подразумевают, что она будет вызываться, пока будет работать компьютер или программа, в которой она работает.

Возможна также организация сложной рекурсии с помощью двух функций. Допустим, есть А и Б. Функция А имеет в своем коде вызов Б, а Б, в свою очередь, указывает компьютеру на необходимость выполнить А. Сложные рекурсии – это выход из целого ряда сложных логических ситуаций для компьютерной логики.

Если читающий эти строки изучал программные циклы, то он, наверное, уже заметил схожесть между ними и рекурсией. В целом они действительно могут выполнять похожие или идентичные задания. С помощью рекурсии удобно делать имитацию работы цикла. Особенно это полезно там, где сами циклы использовать не очень удобно. Схема программной реализации не сильно различается у разных высокоуровневых языков программирования. Но всё же рекурсия в «Паскале» и рекурсия в С или другом языке имеет свои особенности. Может она быть успешно реализована и в низкоуровневых языках вроде «Ассемблера», но это является более проблематичным и затратным по времени.

Деревья рекурсии

Что такое «дерево» в программировании? Это конечное множество, состоящее как минимум из одного узла, который:

  1. Имеет начальный специальный узел, который называют корнем всего дерева.
  2. Остальные узлы находятся в количестве, отличном от нуля, попарно непересекающихся подмножеств, при этом они тоже являются деревом. Все такие формы организации называют поддеревьями главного дерева.

Другими словами: деревья содержат поддеревья, которые содержат ещё деревья, но в меньшем количестве, чем предыдущее дерево. Так продолжается до тех пор, пока в одном из узлов не останется возможности продвигаться далее, и это будет обозначать конец рекурсии. Есть ещё один нюанс насчет схематического изображения: обычные деревья растут снизу вверх, а в программировании они рисуются наоборот. Узлы, не имеющие продолжения, называются конечными узлами. Для удобства обозначения и для удобства используется генеалогическая терминология (предки, дети).

Зачем она применяется в программировании?

Своё применение рекурсия в программировании нашла в решении целого ряда сложных задач. Если необходимо сделать только один вызов, то более легким является применение интеграционного цикла, но при двух и более повторах, чтобы избежать построения цепочки и сделать их выполнение в виде дерева, и применяются рекурсивные ситуации. Для широкого класса задач организация вычислительного процесса таким способом является наиболее оптимальной с точки зрения потребления ресурсов. Так, рекурсия в «Паскале» или другом любом высокоуровневом языке программирования представляет собой вызов функции или процедуры до выполнения условий, независимо от количества внешних вызовов. Другими словами, в программе может быть только одно обращение к подпрограмме, но происходить оно будет до определённого заранее момента. В некотором роде это аналог цикла со своей спецификой использования.

Отличия рекурсии в различных языках программирования

Несмотря на общую схему реализации и конкретное применение в каждом отдельном случае, рекурсия в программировании имеет свои особенности. Это может привести к сложности во время поиска необходимого материала. Но всегда следует помнить: если язык программирования вызывает функции или процедуры, значит, и вызов рекурсии — дело осуществимое. Но наиболее значимые её отличия проявляются при использовании низких и высоких языков программирования. Особенно это касается возможностей программной реализации. Исполнение в конечном итоге зависит от того, какая задача поставлена, в соответствии с ней и пишется рекурсия. Функции и процедуры используются разные, но их цель всегда одна – заставить вызвать самих себя.

Рекурсия – это легко. Как просто запомнить содержание статьи?

Для начинающих понять её, может быть, поначалу сложно, поэтому нужны примеры рекурсии или хотя бы один. Поэтому следует привести небольшой пример из бытовой жизни, который поможет понять саму суть этого механизма достижения целей в программировании. Возьмите два или больше зеркал, поставьте их так, чтобы в одном отображались все остальные. Можно увидеть, что зеркала отображают себя многократно, создавая эффект бесконечности. Вот рекурсии — это, образно говоря, отражения (их будет множество). Как видите, понять несложно, было бы желание. А изучая материалы по программированию, далее можно понять, что рекурсия – это ещё и очень легко выполнимая задача.

продвинутых концепций рекурсии, которые должен знать каждый эффективный программист | by Andre Ye

Рекурсия — это подход к решению проблем, при котором функция вызывает себя в пределах определения функции. Каждая рекурсивная реализация должна иметь два элемента:

  • Базовый вариант или варианты, которые являются завершающими случаями, в которых ответ не ищется в дальнейшем с дополнительной рекурсией.
  • Набор правил (отношение рекурсии), которые сводят другие варианты к базовому, инициируя еще один цикл рекурсии.

Например, давайте рассмотрим задачу печати обратной стороны строки. Результатом ввода «hello» должно быть «olleh». Итерационный метод решения этой задачи заключается в использовании цикла for и распечатке каждого символа от последнего индекса до первого.

Рекурсивный метод будет первым, чтобы создать функцию reverseString , которая принимает строку в качестве параметра. Если длина ввода не равна 0 — это будет базовый или завершающий регистр — мы печатаем последнюю букву и инициируем другой экземпляр reverseString в текущей строке, исключая последний последний (поскольку он был только что напечатан) .

Обратите внимание: поскольку функция вызывается внутри себя, она сама создает цикл for. Кроме того, наличие оператора if перед вызовом другого экземпляра функции обязательно — в противном случае будет выдано RecursionError или RuntimeError , потому что сценарий не видит конца бесконечному циклу. Это похоже на бесконечный цикл , в то время как True .

Давайте посмотрим, как эта рекурсивная функция действует на «hello»:

Повторение более сложных проблем может быть сложной задачей, потому что определение двух его компонентов — отношения рекурсии, отношения между результатом проблемы и результатом ее подзадач; и базовый случай, случай, который можно вычислить напрямую, без каких-либо рекурсивных вызовов.Иногда базовые случаи называют «нижними случаями», поскольку это случаи, когда проблема была сведена к минимальному масштабу.

Рассмотрим, например, треугольник Паскаля, в котором каждое число представляет собой сумму двух вышележащих чисел с единицами по сторонам треугольника. Как можно использовать рекурсию, чтобы найти значение любого значения в точке ( i, j )? Что такое рекуррентное отношение и базовый / завершающий случай?

Повторяющееся соотношение может быть выражено следующим уравнением:

Это очевидно, если взглянуть на график треугольника.Что еще лучше в этой формуле, так это то, что если мы продолжим использовать ее для разбиения любого местоположения ( i, j ) как суммы двух других местоположений, это неизбежно приведет к базовому случаю — 1. Треугольник Паскаля начинается с единиц, а из суммы единиц вырисовывается целая сложная картина.

Как это реализовать?

Для начала давайте найдем набор правил, чтобы определить, когда соблюден базовый вариант — значение ячейки равно 1. Обратите внимание, что единицы появляются при двух условиях: либо они находятся в первом столбце ( j = 0), либо они расположены по диагонали ( i = j ).

Теперь внедрить просто. Если условия базового случая соблюдены, мы возвращаем базовое значение (1). В противном случае мы продолжаем уменьшать проблему до тех пор, пока не достигнем базового случая, на который, как мы определили, неизбежно будут разбиты любые входные данные.

К настоящему времени красота рекурсии уже должна была вас осенить. Здесь мы, по сути, создаем саморазвивающееся дерево в пяти строках кода (это может быть даже три строки, если вы хотите его сократить). Когда мы дважды вызываем функцию pascal , мы инициируем две ветви поиска , каждая из которых инициирует еще две, предполагая, что они не достигли базового варианта.

Это может быть немного волшебно и сбивать с толку, как рекурсия работает так эффективно. Давайте разберемся, как работает рекурсивный алгоритм на примере.

(4, 2) разбивается на (3, 1) и (3, 2), которые являются двумя числами над ним, в соответствии с нашим рекуррентным соотношением. Обратите внимание, что алгоритм на самом деле не знает, что значения этих ячеек равны 3, он просто отмечает их расположение. Мы не знаем и не заботимся о какой-либо ценности, если она не удовлетворяет нашим базовым условиям. Из наших базовых случаев (1) мы можем вычислить другие небазовые местоположения, но сначала должны быть найдены все базовые случаи.

Объяснение рекурсии — Как рекурсия работает в программировании?

Рекурсия означает «решение проблемы посредством решения меньшей версии той же проблемы» или «определение проблемы в терминах самой себя». Это широко используемая идея в программировании для решения сложных проблем путем разбиения их на более простые. В этом блоге мы рассмотрим основы рекурсии и поможем вам развить важные навыки программирования.

Рекурсия часто встречается в математике, где есть много примеров выражений, написанных в терминах самих себя.Вычисление значения n-го факториала и n-го числа Фибоначчи — лучший пример этого. Но рекурсия — это такая же концепция программирования!

  n-й Факториал: n! = п * (п-1)!
Последовательность Фибоначчи: F (n) = F (n-1) + F (n-2)
  

Рекурсия в реальной жизни

Предположим, вы стоите в длинной очереди из людей. Сколько людей стоит прямо за вами в очереди?

Правила
  • Один человек может видеть только человека, стоящего прямо впереди и сзади.Так что нельзя просто оглянуться и посчитать.
  • Каждый человек может задавать вопросы человеку, стоящему впереди или сзади. Как решить эту проблему рекурсивно?
Решение
  • Вы смотрите назад и видите, есть ли там человек. Если нет, то вы можете вернуть ответ «0». Если есть человек, повторите шаг 1 и дождитесь ответа от человека, стоящего позади.
  • Как только человек получает ответ, он добавляет 1 для человека, стоящего за ним, и отвечает человеку, который его спросил, или человеку, стоящему перед ним.

      int peopleCount (Человек curr)
    {
      если (noOneBehind (currPerson))
      {
          возврат 0
      }
      еще
      {
          Человек personBehind = curr.getBehind ()
          вернуть peopleCount (personBehind) + 1
      }
    }
      

Рекурсия в программировании

С точки зрения программирования, рекурсия — это функция, вызывающая себя до тех пор, пока «базовое условие» не станет истинным для получения правильного вывода.

  функция void ()
{
    базовый вариант
    .. .. ...
    function () // рекурсивный вызов
    .. .. ...
}

int main ()
{
    ... .. ...
    функция ()
    ... .. ...
}
  

Другими словами — чтобы решить проблему, мы решаем подзадачу, которая является меньшим экземпляром той же проблемы, а затем используем решение этого меньшего экземпляра для решения исходной проблемы. Чтобы рекурсивный алгоритм работал, меньшие подзадачи должны в конечном итоге прийти к базовому случаю.

Рекурсивный алгоритм состоит из двух частей:

  1. Базовый случай: Условие завершения, при котором функция может немедленно вернуть результат.Это наименьшая версия проблемы, решение которой мы уже знаем.
  2. Рекурсивная структура: Решение проблемы путем решения ее более мелких подзадач, то есть той же проблемы, но для меньшего размера ввода. Здесь функция должна вызывать сама себя, чтобы разложить текущую проблему до более простого уровня.

Стратегия рекурсивного решения проблем

Действия, которые необходимо выполнить
  • Определите базовый случай: подумайте о наименьшей версии проблемы и запишите решение.
  • Define Recursive Structure: Теперь предположим, что у нас есть функция для решения проблемы с заданным размером входных данных. Как мы можем использовать его для меньшего размера ввода и использовать ответ для решения большего размера?
  • Объединить базовый случай и рекурсивную структуру
О чем следует помнить
  • Наш код должен охватывать все допустимые экземпляры с меньшими размерами ввода.
  • У нас должен быть базовый вариант, который не делает рекурсивных вызовов.
  • Когда мы делаем рекурсивный вызов, он должен вызывать меньший экземпляр и продвигаться к базовому случаю.
  • Когда у нас есть правильная рекурсивная структура и базовый случай, рекурсия решит проблему за нас. Это «рекурсивный прыжок веры», когда нам не следует беспокоиться о промежуточных этапах рекурсивных вызовов.

Основные примеры рекурсивных функций

  • Вычислить сумму двух чисел с помощью рекурсии

      сумма (x, y)
    = x, если (y == 0)
    = 1 + sum (x, y-1), если (y> 0)
      
  • Вычислить произведение двух чисел с помощью рекурсии

      произведение (x, y)
    = 0, если (y == 0)
    = сумма (x, произведение (x, y-1), если (y> 0)
      
  • Вычислить степень двух чисел с помощью рекурсии

      мощность (x, y)
    = 1, если (y == 0)
    = product (x, power (x, y-1), если (y> 0)
      

Понимание рекурсии через поиск факториала nth

Факториал неотрицательного целого числа — это умножение всех целых чисел, меньших или равных n.Например. факториал 5 равен 1 * 2 * 3 * 4 * 5 = 120

Рекурсивная структура

Согласно математическому определению факториала числа n, мы можем написать

  н!
= n * (n-1) * (n-2) *…. * 2 * 1
= п * (п-1)!

=> n-й факториал = n * (n-1) -й факториал
  

Если мы вычислим значение факториала (n-1) -й , мы можем легко вычислить значение n-го факториала . Это означает, что мы можем решить проблему размера ввода n с ее меньшей подзадачей размера ввода (n-1) .Другими словами, мы можем решить эту проблему, используя идею рекурсии.

Предположим, что функция fact (n) и fact (n-1) возвращает значение факториала n-й и (n-1) -й соответственно, тогда мы можем написать следующую рекурсивную структуру.

  факт (n) = n * факт (n-1)
  

Базовый корпус

В каждом рекурсивном решении должно быть условие завершения или базовый случай, когда наша рекурсия будет напрямую давать вам результаты, не разбивая их снова на подзадачу.Если мы наблюдаем приведенную выше рекурсивную структуру, то мы обнаруживаем следующую цепочку рекурсивных вызовов:

  факт (n)
= n * факт (n-1)
= п * (п-1) * факт (п-2)
... и так далее
= n * (n-1) * (n-2) * ... * 4 * 3 * 2 * факт (1)
= n * (n-1) * (n-2) * ... * 4 * 3 * 2 * 1 * факт (0)
  

Факториал отрицательного числа не определен, поэтому fact (0) — это наименьшая версия проблемы факториала, на которой наша рекурсия завершится. Итак, n = 0 — это базовый случай, который вернет значение 1.

Рекурсивный псевдокод n-го факториала
  int факт (int n)
{
    если (n == 0)
        возврат 1
    вернуть n * факт (n-1)
}
  

Как работает рекурсия в фоновом режиме?

Если мы нарисуем поток рекурсии вышеупомянутого псевдокода, можно найти этот шаблон: мы вызываем fact (0) в последнюю очередь, но сначала возвращает значение. Точно так же мы сначала вызываем fact (n), но возвращаем значение последним. Вы нашли порядка Last In First Out (LIFO) для рекурсивных вызовов и возвращаемых значений? Да, вы поняли! За сценой компилятор использует структуру данных стека для имитации рекурсии и получения правильного вывода.Мы называем этот стек: Стек вызовов !

  • Порядок рекурсивных вызовов: большая проблема к меньшей проблеме

    факт (n) -> факт (n-1) …-> факт (i) -> …-> факт (1) -> факт (0)

  • Порядок возвращаемых значений: меньшая проблема — большая проблема

    факт (0) -> факт (1) …-> факт (i) -> …-> факт (n-1) -> факт (n)

Как идея стека вызовов работает в рекурсии?

  • Информация о выполнении рекурсивной функции хранится в стеке вызовов.Он содержит подробную информацию о выполнении: текущее состояние потока управления, локальные переменные и другую внутреннюю информацию. Когда какая-либо функция вызывается из main (), ей выделяется память в стеке.
  • Во время рекурсии, когда функция вызывает ту же функцию для меньшего размера ввода, ей выделяется память, и она идет вверху стека вызовов.
  • Память для вызываемой функции выделяется поверх памяти, выделенной для вызывающей функции, и для каждого вызова функции создается отдельная копия локальных переменных.
  • Когда достигается базовый вариант, функция возвращает свое значение функции, которой она вызывается, память освобождается, и процесс продолжается.
Рекурсионные визуализации для вычисления фактов (5)

Рекурсионные визуализации для вычисления фактов (3)

Источник изображения: mit.edu

Известные рекурсивные алгоритмы

Перевернуть массив
  • Рекурсивная структура

      реверс (A [], l, r)
    - своп (A [l], A [r])
    - реверс (A, l + 1, r-1)
      
  • Базовый случай: если (l> = r), то вернуть
  • Отношение повторяемости: T (n) = T (n-2) + c, сложность времени = O (n)

Нахождение НОД двух чисел

Нахождение n-го Фибоначчи

Ханойская башня

Двоичный поиск
  • Рекурсивная структура

      binarySearch (A [], l, r, k)
    - если A [mid] = k, вернуть mid
    - если (A [mid]> k), binarySearch (A [], l, mid-1, k)
    - если (A [mid]  
  • Базовый случай: Если (l> r), то вернуть -1
  • Отношение повторяемости: T (n) = T (n / 2) + C, сложность времени = O (log n)

Сортировка слиянием
  • Рекурсивная структура

      mergeSort (A [], l, r)
    - mergeSort (A, l, mid)
    - mergeSort (A, mid + 1, r)
    - объединить (A, l, mid, r)
      
  • Базовый случай: if (l == r) then return, Это случай одноэлементного массива.
  • Соотношение повторяемости: T (n) = 2 T (n / 2) + cn, временная сложность = O (n log n)

Быстрая сортировка
  • Рекурсивная структура

      quickSort (A [], l, r)
    - стержень = раздел (A, l, r)
    - quickSort (A, l, pivot - 1)
    - quickSort (A, pivot + 1, r)
      
  • Базовый случай: если (l> = r), то вернуть (Подумайте!)
  • Соотношение повторяемости: T (n) = Sum (i = от 0 до n-1) [T (i) + T (n-i-1)] / n, сложность времени = O (nlogn) [Анализ среднего случая]

Обратный связанный список

Пост-заказный обход двоичного дерева

Вывести все перестановки заданной строки
  • Рекурсивная структура

      переставить (S [], l, r)
    =>
    для (я = от 1 до г)
    {
      своп (S [l], S [i])
      переставить (S, l + 1, r)
      своп (S [l], S [i])
    }
      
  • Базовый случай: если (l == r), то выведите (A)
  • Соотношение повторяемости: T (n) = сумма (i = от 0 до n-1) [T (n-i) + c], сложность времени = O (n!)

Итерация против рекурсии

Способ реализации

  • Итерация - Реализована с использованием циклов и определяется значением управляющих переменных.
  • Рекурсия - Реализуется с использованием вызовов функций и определяется значением параметров функции, хранящихся в стеке вызовов.

Характер ошибки кода

  • Итерация - Бесконечный цикл возникает из-за ошибки в назначении или приращении итератора, или из-за условия завершения или неправильного условия завершения. Это потребляет системные ресурсы, такие как время процессора или память, и останавливает выполнение программы.
  • Рекурсия - бесконечная рекурсия может возникнуть из-за отсутствия базового случая или неправильного базового случая.Это вызовет сценарий переполнения стека, который может привести к сбою ЦП.

Анализ кода

  • Итерация - В большинстве случаев анализ итеративного кода прост и интуитивно понятен.
  • Рекурсия - Анализ рекурсивного кода в большинстве случаев затруднен из-за сложных рекуррентных отношений.

Исполнение кода

  • Итерация - Итерация не связана с такими накладными расходами.
  • Рекурсия - Рекурсия обычно медленнее, потому что она связана с большими накладными расходами на вызовы функций. Вызовы функций должны храниться в стеке, чтобы можно было вернуться к вызывающим функциям.

Размер кода

  • Итерация - Размер итеративного кода обычно больше.
  • Рекурсия - Рекурсия уменьшает размер кода.

Переполнение стека при рекурсии

Когда мы вызываем рекурсивную функцию, адрес возврата и аргументы помещаются в стек вызовов.Стек конечен, поэтому, если рекурсия будет слишком глубокой, у вас в конечном итоге закончится место в стеке. Это также называется переполнением стека в рекурсии. В некоторых ситуациях, если рекурсивная функция является хвостовой рекурсивной, некоторые компиляторы могут оптимизировать рекурсивный вызов, превратив его в переход. Популярная причина ошибки переполнения стека:

  • У рекурсивной функции не будет никакого базового случая.
  • Рекурсивный вызов функции с неправильным базовым случаем

Распространенные ошибки в рекурсивных реализациях

Вот два распространенных способа, по которым рекурсивная реализация может пойти не так:

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

Ищите их при отладке. С другой стороны, бесконечный цикл в итеративной реализации обычно становится ошибкой переполнения стека в рекурсивной реализации. Рекурсивная программа с ошибками дает сбой быстрее.

Применение рекурсии в решении проблем

  • Разделяй и властвуй Приближайся, уменьшайся и властвуй
  • Алгоритмы поиска и сортировки: двоичный поиск, сортировка слиянием, быстрая сортировка и т. Д.
  • Решение проблем с использованием рекурсивного обхода дерева
  • Решение проблем с использованием DFS на графике
  • Решение задач динамического программирования
  • Решение проблем с помощью функции Backtracking
  • Решение проблем связанных списков
  • Построение аппроксимационных алгоритмов

Концепции для дальнейшего изучения в рекурсии

  • Типы рекурсии
  • Рекурсия хвоста и рекурсивные оптимизации
  • Анализ рекурсии с использованием метода дерева рекурсии
  • Анализ рекурсии с использованием основной теоремы
  • Идея функционального программирования

Проблемы кодирования для практики в рекурсии

  • Нахождение НОД двух чисел, Нахождение n-го Фибоначчи
  • Рекурсивный двоичный поиск, алгоритм Карацубы
  • Ханойская башня, проблема Иосифа Флавия
  • Сортировка слиянием, быстрая сортировка
  • Медиана двух отсортированных массивов, K-й наименьший элемент двух отсортированных массивов
  • Проблема заполнения наводнения, генерация всех перестановок строки

Ссылки на контент

Если у вас есть идеи / вопросы / сомнения / отзывы, оставьте комментарий ниже или напишите нам по адресу contact @ Enjoyyalgorithms.com . Наслаждайтесь обучением, наслаждайтесь кодированием, наслаждайтесь алгоритмами!

Говоря простым языком, что такое рекурсия?

Чтобы объяснить рекурсию, я использую комбинацию разных объяснений, обычно пытаясь оба:

  • объясните концепцию,
  • объясните, почему это важно,
  • объясните, как это получить.

Для начала, Wolfram | Alpha дает более простое определение, чем Википедия:

Выражение, в котором каждый член генерируется путем повторения определенной математической операции.


Математика

Если ваш ученик (или человек, которого вы тоже объясняете, с этого момента я буду говорить студент) имеет хотя бы некоторую математическую подготовку, он, очевидно, уже столкнулся с рекурсией, изучая ряды и их понятие рекурсивности и их рекуррентное отношение.

Очень хороший способ начать - затем продемонстрировать серию и сказать, что это очень просто, о чем рекурсия:

  • математическая функция ...
  • ... который вызывает себя для вычисления значения, соответствующего n-му элементу ...
  • ... и который определяет некоторые границы.

Обычно в лучшем случае вы слышите «ага, что-то», потому что они все еще не используют его, или, что более вероятно, просто очень глубоко храпит.


Примеры кодирования

В остальном, это фактически подробная версия того, что я представил в приложении моего ответа на вопрос, на который вы указали относительно указателей (плохая игра слов).

На этом этапе мои ученики обычно знают, как что-то напечатать на экране.Предполагая, что мы используем C, они знают, как напечатать один символ, используя write или printf . Они также знают о контурах управления.

Я обычно прибегаю к нескольким повторяющимся и простым задачам программирования, пока они не получат это:

Факториал

Факториал - это очень простая для понимания математическая концепция, реализация которой очень близка к ее математическому представлению. Однако сначала они могут этого не понять.

Алфавиты

Версия с алфавитом интересно научить их думать об упорядочивании своих рекурсивных операторов.Как и в случае с указателями, они просто случайным образом бросают вам строки. Дело в том, чтобы привести их к осознанию того, что цикл можно инвертировать, либо изменив условия ИЛИ , просто изменив порядок операторов в вашей функции. Вот здесь и помогает распечатка алфавита, поскольку для них это что-то визуальное. Просто попросите их написать функцию, которая будет печатать один символ для каждого вызова и рекурсивно вызывать себя для записи следующего (или предыдущего) символа.

Поклонники FP, пропустите тот факт, что печать в выходной поток является побочным эффектом... Давайте не будем слишком раздражать FP-фронт. (Но если вы используете язык с поддержкой списков, не стесняйтесь объединять в список на каждой итерации и просто распечатывать окончательный результат. Но обычно я начинаю их с C, что, к сожалению, не лучший вариант для такого рода проблем и концепций) .

Возведение в степень

Задача возведения в степень немного сложнее ( на данном этапе обучения). Очевидно, что концепция точно такая же, как и для факториала, и нет дополнительной сложности... за исключением того, что у вас есть несколько параметров. И этого обычно достаточно, чтобы сбить с толку людей и сбить их с толку вначале.

Его простая форма:

можно выразить как повторение:

Жестче

После того, как эти простые задачи будут показаны И повторно реализованы в учебных пособиях, вы можете давать немного более сложные (но очень классические) упражнения:

  • Числа Фибоначчи,
  • Наибольший общий делитель,
  • Задача 8 ферзей,
  • Игра Башни Ханоя,
  • И если у вас есть графическая среда (или вы можете предоставить заглушки кода для нее или для вывода терминала, или они уже могут этим управлять), то такие вещи, как:
  • А для практических примеров подумайте о том, чтобы написать:
    • алгоритм обхода дерева,
    • простой анализатор математических выражений,
    • игра-тральщик.

Примечание: Опять же, некоторые из них действительно не сложнее ... Они просто подходят к проблеме с точно такой же точки зрения или немного с другой. Но практика ведет к совершенству.


Помощники

A Номер ссылки

Немного чтения никогда не помешает. Что ж, сначала будет, и они почувствуют себя еще более потерянными. Это из тех вещей, которые растут в вас и сидят на затылке, пока однажды вы не поймете, что наконец поняли.А потом вы вспоминаете то, что читали. На данный момент подойдут рекурсия, рекурсия в информатике и страницы отношения рекурсии в Википедии.

Уровень / Глубина

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

Схема расположения ящиков в стопке

Отступ напечатанного результата (или вывода уровня) также помогает, поскольку он дает другое визуальное представление о том, что делает ваша программа, открывая и закрывая контексты стека, такие как ящики или папки в проводнике файловой системы.

Рекурсивные сокращения

Если ваш ученик уже немного разбирается в компьютерной культуре, он, возможно, уже использует некоторые проекты / программное обеспечение с именами, использующими рекурсивные сокращения. Некоторое время это было традицией, особенно в проектах GNU. Некоторые примеры включают:

Рекурсивный:

  • GNU - «GNU - это не Unix»
  • Нагиос - «Нагиос не будет настаивать на святости»
  • PHP - «Препроцессор гипертекста PHP» (и первоначально «Персональная домашняя страница»)
  • Wine - «Вино не эмулятор»
  • Zile - "Zile Is Lossy Emacs"

Взаимно рекурсивный:

  • HURD - «HIRD демонов, заменяющих Unix» (где HIRD - «HURD интерфейсов, представляющих глубину»)

Пусть они попробуют придумать свои собственные.

Точно так же есть много случаев рекурсивного юмора, вроде исправления рекурсивного поиска Google. Для получения дополнительной информации о рекурсии прочтите этот ответ.


Подводные камни и дальнейшее обучение

Некоторые проблемы, с которыми обычно сталкиваются люди и на которые нужно знать ответы.

Почему, боже почему ???

Зачем вы это делаете? Хорошая, но неочевидная причина в том, что часто проще выразить проблему таким образом. Не очень хорошая, но очевидная причина в том, что для этого часто требуется меньше набора текста (хотя не заставляйте их чувствовать себя так уж нелепо из-за простого использования рекурсии...).

Некоторые проблемы определенно легче решить при использовании рекурсивного подхода. Как правило, любая проблема, которую можно решить с помощью парадигмы «Разделяй и властвуй», подойдет для алгоритма разветвленной рекурсии.

Что опять N ??

Почему мой n или (каково бы ни было имя вашей переменной) каждый раз различается? У новичков обычно возникают проблемы с пониманием того, что такое переменная и параметр, и как вещи с именем n в вашей программе могут иметь разные значения.Так что теперь, если это значение находится в цикле управления или рекурсии, это еще хуже! Будьте вежливы и не используйте везде одни и те же имена переменных и дайте понять, что параметры - это просто переменные .

Конечные условия

Как определить конечное состояние? Это легко, просто попросите их сказать шаги вслух. Например, для факториала начните с 5, затем с 4, затем ... до 0.

Дьявол в деталях

Не говорите о таких вещах, как оптимизация хвостовых вызовов.Знаю, знаю, TCO - это хорошо, но сначала им все равно. Дайте им немного времени, чтобы осмыслить процесс так, как это им подходит. Позже вы можете снова разрушить их мир, но дайте им отдохнуть.

Точно так же не говорите прямо с первой лекции о стеке вызовов, его потреблении памяти и ... ну ... переполнении стека. Я часто обучаю студентов в частном порядке, которые показывают мне лекции, где у них есть 50 слайдов о , все, что нужно знать о рекурсии, когда они едва могут правильно написать цикл на этом этапе.Это хороший пример того, как ссылка поможет , позже , но прямо сейчас вас глубоко сбивает с толку.

Но, пожалуйста, в свое время проясните, что есть причины для выбора итеративного или рекурсивного пути.

Взаимная рекурсия

Мы видели, что функции могут быть рекурсивными и даже иметь несколько точек вызова (8 ферзей, Ханой, Фибоначчи или даже алгоритм исследования для тральщика). Но как насчет взаимно рекурсивных вызовов? Здесь также начните с математики. f (x) = g (x) + h (x) , где g (x) = f (x) + l (x) и h и l , просто делайте разные вещи.

Использование простых математических рядов упрощает написание и реализацию, поскольку контракт четко определяется выражениями. Например, женские и мужские последовательности Хофштадтера:

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

Что такое рекурсия и когда ее использовать?

Рекурсия тесно связана с функциональным программированием. Мы действительно используем рекурсию больше, чем императивные программисты. Но мы также используем итерацию. В этом выпуске мы поговорим о том, что такое рекурсия, как ее использовать, когда использовать, а когда не использовать.








Что такое рекурсия и когда ее использовать?

Расшифровка стенограммы

Эрик Норманд:… это рекурсия, и когда я должен ее использовать? К концу этого эпизода вы будете знать, что это такое, как его использовать, зачем его использовать и особенно, когда его не использовать.

Привет, меня зовут Эрик Норманд. Я помогаю людям развиваться с помощью функционального программирования.

Рекурсия - важная часть функционального программирования. Это возможно в любой парадигме, но часто ассоциируется с функциональным программированием, как правило, профессорами из лучших побуждений, которые хотят заставить людей думать по-другому, когда они преподают функциональное программирование.

Они могут сказать, что этот язык функциональный, в нем нет циклов for. В нем нет никаких циклов, никаких итераций.Вы собираетесь делать рекурсию. Я знаю, что они имеют в виду хорошо. Они хотят, чтобы вы чему-то научились, но это часто расстраивает, потому что во многих функциональных языках есть циклы.

Я хочу сказать, что в функциональном программировании мы используем и итерацию, и рекурсию. В этом видео, в этом уроке мы поговорим о том, когда какие именно использовать.

Что такое рекурсия? Действительно простая концепция. Это когда функция определяется в терминах самой себя. По сути, если функция внутри своего определения вызывает себя, это рекурсия.Очень просто.

Есть еще одна вещь, называемая взаимной рекурсией, потому что это всего лишь одна функция. Что, если у вас есть две функции, которые вызывают друг друга? Это взаимная рекурсия. Функция A вызывает функцию B, а функция B вызывает функцию A.

Почему мы ее используем? Мы делаем это в реальном мире. Это всякий раз, когда у вас есть проблема, которую невозможно решить в одиночку. Чтобы решить проблему, вам нужно разделить ее на части. Вы можете сказать: «Послушайте, нам нужно построить это огромное здание.Это большое прямоугольное здание из кирпича. Как мы собираемся начать? Я не могу просто класть кирпичи.

Ты найдешь своих друзей, найди других строителей. Вы скажете: «Сделай северную стену. Вы делаете южную стену, восточную стену, западную стену ». Вы решаете проблему. Вероятно, у них будет небольшая команда. Вы говорите: «Начни с этой стороны. Я начну с этой стороны. Мы собираемся решить эту проблему ».

Мы делаем это постоянно. «Эй, ты можешь помочь мне посчитать эти вещи? Разбить стек пополам? Вы забираете эту половину.Я возьму эту половину. Если он все еще слишком велик, вы можете снова сломать его пополам. Вы можете отправить его кому-нибудь другому.

Для нас это очень естественно. Мы делаем это все время. Вот почему мы это делаем, потому что некоторые проблемы гораздо естественнее решать рекурсивно, чем начинать с самого начала и повторять.

Еще можно. На самом деле они такие же. В конце дня, если вы посчитаете стопку бумаг по одной, начиная сверху, вы получите такой же ответ, как если бы вы разбили задачу на две, посчитали их отдельно, а затем сложили это вверх.Вы получите тот же ответ.

Очень часто генерируемый машинный код очень похож. Рекурсия и итерация - вы всегда можете конвертировать между ними. Это еще одна вещь, которую иногда понимают неправильно.

Когда мы это сделаем? Как я уже говорил ранее, если проблема является естественной рекурсивной… я имею в виду свои заметки здесь.

Если проблема - это то, что вы можете сломать, то это легко. Когда это естественно? Когда его легко разбить на части.

Если у вас есть стопка бумаг и вы просто считаете их, неважно, где вы ее сломаете, вы можете разрезать ее примерно пополам. Это хорошее свойство проблемы. Если у вас четыре стены, их легко разделить на четыре части. Разбить это легко.

Другое дело, что вы знаете, когда остановиться. Если я продолжу разбивать эту задачу о подсчете листов пополам, наполовину и наполовину, в какой-то момент у меня просто останется одна бумага. Больше никаких расставаний.Я знаю, когда остановиться. Это один. Эту маленькую проблему легко решить.

Вот эти две вещи. Легко решить проблему, и легко узнать ответ и когда остановиться. Это то, что делает рекурсию действительно естественной.

Другой способ очень похож, но стоит отметить отдельно, когда ваша структура данных является рекурсивной. Если у вас есть дерево, деревья рекурсивны. У вас есть узел, и у него есть дочерние узлы. Эти дочерние узлы имеют больше узлов, а те - больше узлов.

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

Рекурсивная структура данных, а значит, рекурсия, вероятно, является ответом на этот вопрос. Если вы попытаетесь сделать это с помощью итераций, это, скажем, будет менее естественно. Вероятно, вам придется прибегнуть к фальшивой рекурсии.

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

Если вам нужно пройти по структуре каталогов на жестком диске с помощью цикла for, вы, вероятно, собираетесь создать стек. Вы собираетесь составить небольшую стопку: «Мне нужно снова посетить эту штуку, но я собираюсь положить ее в стопку, а затем посетить этот каталог.«Вы постоянно говорите:« О, есть еще работа, но я еще не там, поэтому я просто собираюсь положить ее в стопку ».

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

Тогда возникает вопрос, когда нет. Я думаю, что функциональное программирование и рекурсия имеют эту взаимосвязь, потому что - это по моему опыту - профессора пытаются научить вас чему-то новому. Они находятся в блоке функционального программирования.

Они такие: «О, это идеальное время для обучения рекурсии, потому что функциональным программированием студенты занимались для циклов всю свою жизнь.Наконец, они могут делать все в функциональном режиме. Давайте научим их рекурсии. Избавьтесь от этого зацикленного мышления ».

Это доблестный поступок, но проблема в том, что они думают, что это все, что вам нужно делать в функциональном программировании. Так думают студенты.

У меня есть друг, который сказал бы: «Ну, я не люблю Lisp, потому что в нем нет циклов. Вы должны делать все с помощью рекурсии ». Это неправда. В Лиспе много петель.

В Clojure много циклов. Common Lisp имеет шесть или семь различных типов циклов.Есть цикл while, есть вещь, называемая Loop, похожая на цикл for. Перебираем список. Повторяется несколько раз. Существует множество различных циклов, больше циклов, чем в Java или JavaScript.

Java и JavaScript, у них в основном есть цикл for. Теперь у вас есть для каждого, и есть цикл while, и все.

Когда вы им не пользуетесь? Вернемся к этому. Общее правило - когда это более естественно, более понятно, легче реализовать в итерации с использованием цикла for или чего-то еще.Когда выполнить итерацию проще, чем повторять, вам обязательно следует использовать итерацию. Когда проще выполнить итерацию, следует использовать цикл.

Рекурсия - не всегда лучший ответ. Я просто хочу рассказать об этом. Мне нравится функциональное программирование. Я верю в это, но хочу, чтобы вы услышали это от человека, который действительно любит функциональное программирование. Рекурсия - это еще не все. Это не всегда ответ.

Кроме того, иногда в зависимости от виртуальной машины, на которой вы работаете, или от имеющейся у вас среды выполнения, от того, как она скомпилирована, у вас могут возникнуть проблемы с рекурсией.Это может израсходовать ваш стек. Вы получаете переполнение стека, потому что они не оптимизируют должным образом так называемые хвостовые вызовы.

Хвостовой вызов - это если я выполняю рекурсию и в конце вызываю любую функцию. Как будто я А, и последнее, что я делаю, это звоню Б, это называется хвостовой звонок. На самом деле мне не нужно добавлять в стек, потому что я готов. Я А. Я закончил. Больше делать нечего. Я собираюсь вызвать B, чтобы вы могли повторно использовать этот кадр стека.

Это позволяет вам звонить себе снова и снова.Если я вызываю себя снова, и снова, и снова, и снова, мне не нужен новый фрейм стека, если это последнее, что я делаю. Если я вспоминаю что-то, к чему я собираюсь вернуться, мне нужен фрейм стека, но очень часто это не так.

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

Вот и все. Это все, что я могу сказать о рекурсии.Еще кое-что. Я просто также хочу подчеркнуть, что вы всегда можете переключаться между ними. Рекурсивную реализацию можно переписать как итерацию, а итеративную вещь можно записать как эквивалентную рекурсию. Они полностью эквивалентны.

Вы всегда можете поэкспериментировать, чтобы увидеть, какая из них кажется более естественной, более нормальной. Я бы сказал, что если вы занимаетесь функциональным программированием, вам следует этим заняться. Если ваша естественная склонность - попробовать итерацию, попробуйте. Попробуйте рекурсию.

Напомним.Рекурсия - это функция, определенная в терминах самой себя или функции, вызывающей сама себя. Это рекурсия. Многие проблемы являются естественно рекурсивными, поэтому математики и программисты обнаружили, что определение решения рекурсивно также очень естественно, но не всегда естественно. Иногда итерация более ясна.

Юморите меня немного. Поскольку вы можете реализовать любую итерацию с точки зрения рекурсии, я предлагаю вам взглянуть на какой-нибудь код, который у вас есть, с неприятной частью итерации, например, с неприятным циклом for или чем-то в этом роде.Посмотрите, сможете ли вы написать это рекурсивно. Посмотрите, сможете ли вы найти лучшую, более естественную рекурсивную реализацию.

Просто попробуйте. Вы всегда можете выбросить код, но просто попробуйте.

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

Знаете что? Я забыл поговорить о том, как это сделать, поэтому хочу поднять этот вопрос прямо сейчас. С рекурсией действительно… О нет, я уже говорил об этом.Я говорил об этом. Я просто упомяну об этом еще раз.

Как ты узнал, когда закончить. Обычно вы говорите о самом простом, самом маленьком случае. Если я добавляю числа в список, самым простым и минимальным случаем будет… Подумайте об этом на секунду. Это будет пустой список. Пустой список - это просто. Будет ноль.

Это тот, который вы найдете в конце. Это легко определить. Затем вы должны определить, как мне разбить проблему так, чтобы она стала такой маленькой, даже если в ней есть что-то одно.Это просто. Это просто число, которое вы складываете. Это всего лишь одна вещь.

Вот те два дела. Пустой список, единственный список, тоже очень простой, тогда у вас есть список из многих. Вам просто нужно определить, как это разбить. Как только вы его разбиваете, он вызывает сам себя на этой разбитой части, поэтому вы разбиваете массив на две части или что-то еще. Тогда, в конце концов, будет либо ноль, либо единица. Тогда это очень легко определить.

Вот и все. Знайте, когда нужно закончить, знайте, как решить проблему, а затем, что вам нужно делать каждый раз, если это не функциональная вещь.Иногда вам нужно сделать что-то вроде распечатки или чего-то подобного.

Пожалуйста, попробуйте найти что-то, что, по вашему мнению, не так естественно, и напишите это рекурсивно, просто чтобы попробовать. Просто потренируйтесь в использовании рекурсии.

Вот еще одно одолжение, которое вы можете мне сделать. Если вам это нравится, прокомментируйте, подпишитесь или поделитесь с кем-то, кто, по вашему мнению, может это использовать. Мы работаем в командах, и если вы считаете, что кто-то из вашей команды должен узнать о рекурсии, просто поделитесь этим с ними.Спасибо.

Если вам нужно не согласиться со мной, [смеется], если вы не думаете, что рекурсия более естественна, если вы думаете, что это так, но я ошибся в объяснении, прокомментируйте. Свяжитесь со мной.

Вы можете связаться со мной по электронной почте [email protected] Я также в Твиттере @ericnormand, и я тоже пытаюсь войти в LinkedIn, поэтому, пожалуйста, найдите меня там, и мы свяжемся с вами.

Отлично. До скорого.

R Рекурсия (рекурсивная функция) с примером

В этом руководстве вы научитесь создавать рекурсивную функцию (функцию, которая вызывает себя) в программировании на R.

Функция, которая вызывает сама себя, называется рекурсивной функцией, и этот метод известен как рекурсия.

Этот специальный метод программирования можно использовать для решения проблем, разбивая их на более мелкие и простые подзадачи.

Пример может помочь прояснить эту концепцию.

Давайте возьмем пример нахождения факториала числа. Факториал положительного целого числа определяется как произведение всех целых чисел от 1 до этого числа. Например, факториал 5 (обозначается как 5! ) будет

.
 5! = 1 * 2 * 3 * 4 * 5 = 120 

Эту задачу нахождения факториала 5 можно разбить на подзадачу умножения факториала 4 на 5.

 5! = 5 * 4!
 

Или, в более общем смысле,

 н! = п * (п-1)!
 

Теперь мы можем продолжать это, пока не достигнем 0! , то есть 1 .

Реализация этого представлена ​​ниже.


Пример: рекурсивная функция в R

  # Рекурсивная функция для поиска факториала
recursive.factorial <- function (x) {
если (x == 0) возврат (1)
иначе return (x * recursive.factorial (x-1))
}
  

Здесь у нас есть функция, которая вызывает сама себя.Что-то вроде recursive.factorial (x) превратится в x * recursive.factorial (x) , пока x не станет равным 0 .

Когда x становится 0 , мы возвращаем 1 , поскольку факториал 0 равен 1 . Это очень важное условие завершения.

Без этого рекурсия не закончится и будет продолжаться бесконечно (теоретически). Вот несколько примеров вызовов нашей функции.

 > рекурсивный.факторный (0)
[1] 1
> recursive.factorial (5)
[1] 120
> recursive.factorial (7)
[1] 5040
  

Использование рекурсии часто делает код короче и выглядит чистым.

Однако иногда бывает трудно проследить логику кода. Может быть трудно думать о проблеме рекурсивно.

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

Посмотрите эти примеры, чтобы узнать больше:


Руководства и примечания по рекурсии и возврату | Базовое программирование

Когда функция вызывает саму себя, она вызывает рекурсию. Тем, кто смотрел фильм «Начало», будет легче. Леонардо видел сон, в этом сне ему приснился еще один сон, в этом сне ему приснился еще один сон, и это продолжается. Это похоже на то, что есть функция с именем $$ dream () $$, и мы просто вызываем ее сама по себе.

  функция мечта ()
    печать "Сновидения"
    мечтать()
  

Рекурсия полезна при решении проблем, которые можно разбить на более мелкие задачи того же типа . Но когда дело доходит до решения проблем с использованием рекурсии, необходимо позаботиться о нескольких вещах. Давайте возьмем простой пример и попробуем разобраться в них. Ниже приводится псевдокод поиска факториала заданного числа $$ X $$ с использованием рекурсии.

  функция факториал (x)
    if x is 0 // базовый случай
        возврат 1
    return x * factorial (x-1) // разбить на более мелкие проблемы
  

На следующем изображении показано, как это работает для $$ factorial (5) $$.

Базовый случай: Любой рекурсивный метод должен иметь условие завершения. Завершающее условие - это условие, для которого ответ уже известен, и нам просто нужно его вернуть. Например, для задачи факториала мы знаем, что $$ factorial (0) = 1 $$, поэтому, когда $$ x $$ равен 0, мы просто возвращаем 1, в противном случае мы разбиваемся на меньшую задачу, т.е. находим факториал $$ x-1. $$. Если мы не включим базовый случай, функция будет продолжать вызывать себя и в конечном итоге приведет к переполнению стека.Например, приведенная выше функция $$ dream () $$ не имеет базового случая. Если вы напишете для него код на любом языке, он выдаст ошибку во время выполнения.

Количество рекурсивных вызовов : Существует верхний предел количества рекурсивных вызовов, которые могут быть выполнены. Чтобы предотвратить это, убедитесь, что ваш базовый случай достигнут до того, как превысит лимит размера стека.

Итак, если мы хотим решить проблему с помощью рекурсии, нам нужно убедиться, что:

  • Проблема может быть разбита на более мелкие проблемы того же типа .
  • У проблемы есть несколько базовых случаев.
  • Базовый случай достигается до превышения предельного размера стека.

Отслеживание с возвратом:

Итак, решая задачу с помощью рекурсии, мы разбиваем данную задачу на более мелкие. Допустим, у нас есть проблема $$ A $$, и мы разделили ее на три более мелкие задачи: $$ B $$, $$ C $$ и $$ D $$. Теперь может случиться так, что решение $$ A $$ не зависит от всех трех подзадач, на самом деле мы даже не знаем, от какой из них оно зависит.
Возьмем ситуацию. Предположим, вы стоите перед тремя туннелями, в конце одного из которых находится мешок с золотом, но вы не знаете, в каком из них. Итак, вы попробуете все три. Сначала войдите в туннель $$ 1 $$, если это не тот, затем выйдите из него и войдите в туннель $$ 2 $$, и снова, если это не тот, выйдите из него и войдите в туннель $$ 3 $$. Таким образом, в основном при поиске с возвратом мы пытаемся решить подзадачу, и если мы не достигаем желаемого решения, то отменяем все, что мы сделали для решения этой подзадачи, и пытаемся решить другую подзадачу.

Возьмем стандартную задачу.
N-ферзей Задача: Для шахматной доски, имеющей $$ N \ умножить на N $$ клеток, нам нужно разместить $$ N $$ ферзей таким образом, чтобы ни один ферзь не подвергался атаке со стороны другого ферзя. Ферзь может атаковать по горизонтали, вертикали и диагонали.

Итак, изначально у нас есть $$ N \ раз N $$ неатакированных ячеек, куда нам нужно разместить $$ N $$ ферзей. Давайте поместим первого ферзя в ячейку $$ (i, j) $$, так что теперь количество не атакованных клеток уменьшено, и количество ферзей, которые будут размещены, составит $$ N-1 $$.Поместите следующего ферзя в какую-нибудь не атакованную клетку. Это снова уменьшает количество не атакованных клеток, и количество ферзей, которые нужно разместить, становится $$ N-2 $$. Продолжайте делать это, пока выполняются следующие условия.

  • Количество не атакованных ячеек не $$ 0 $$.
  • Количество размещаемых ферзей не превышает $$ 0 $$.

Если количество ферзей становится $$ 0 $$, значит, все кончено, мы нашли решение. Но если количество не атакованных ячеек становится $$ 0 $$, то нам нужно вернуться назад, т.е.е. удалить последнего размещенного ферзя из текущей ячейки и поместить его в другую ячейку. Мы делаем это рекурсивно.
Полный алгоритм представлен ниже:

  is_attacked (x, y, доска [] [], N)
    // проверка строки и столбца
    если любая ячейка в x-й строке равна 1
        вернуть истину
    если любая ячейка в y-м столбце равна 1
        вернуть истину

    // проверка диагоналей
    если любая ячейка (p, q), имеющая p + q = x + y, равна 1
        вернуть истину
    если любая ячейка (p, q), имеющая p-q = x-y, равна 1
        вернуть истину
    вернуть ложь


N-Queens (доска [] [], N)
    if N равно 0 // Все ферзя расставлены
        вернуть истину
    для i = от 1 до N {
        для j = 1 до N {
            если is_attacked (i, j, board, N) истинно
                пропустить и перейти к следующей ячейке
            board [i] [j] = 1 // Поместите текущего ферзя в ячейку (i, j)
            if N-Queens (board, N-1) true // Решить подзадачу
                return true // если решение найдено return true
            board [i] [j] = 0 / * если решение не найдено, отмените все изменения
                                       были сделаны i.e., удалить текущего ферзя из (i, j) * /
        }
    }
    вернуть ложь
  
Вот как это работает для $$ N = 4 $$.

Итак, в конце получается следующее решение:

Итак, очевидно, что приведенный выше алгоритм пытается решить подзадачу, если это не приводит к решению, он отменяет все внесенные изменения и решает следующую подзадачу. Если решение не существует $$ (N = 2) $$, оно возвращает $$ false $$.

Предоставил: Вайбхав Джаймини

упражнений по программированию на C: Рекурсия - w3resource

1. Напишите программу на языке C для вывода первых 50 натуральных чисел с помощью рекурсии. Перейдите в редактор
Ожидаемый результат :

2. Напишите программу на языке C для вычисления суммы чисел от 1 до n с помощью рекурсии. Перейдите в редактор
Test Data:
Введите последнее число диапазона, начиная с 1: 5
Ожидаемый результат :

3. Напишите программу на языке C для печати ряда Фибоначчи с использованием рекурсии. Зайдите в редактор
Test Data:
Введите количество терминов для Серии ( Ожидаемый результат :

Введите количество терминов для серии (

Щелкните меня, чтобы увидеть решение

4. Напишите программу на языке C для печати элементов массива с помощью рекурсии. Перейдите в редактор
Test Data:
Введите количество элементов, которые будут храниться в массиве: 6
Введите 6 элементов в массив:
элемент - 0: 2
элемент - 1: 4
элемент - 2: 6
элемент - 3: 8 элемент
- 4: 10 элемент
- 5: 12
Ожидаемый результат :

 Элементы в массиве: 2 4 6 8 10 12
 

Щелкните меня, чтобы увидеть решение

5. Напишите программу на языке C для подсчета цифр заданного числа с помощью рекурсии. Перейдите в редактор
Test Data:
Введите число: 50
Ожидаемый результат :

 Количество цифр в номере: 2
 

Щелкните меня, чтобы увидеть решение

6. Напишите программу на языке C, чтобы найти сумму цифр числа с помощью рекурсии. Перейдите в редактор
Test Data:
Введите любое число, чтобы найти сумму цифр: 25
Ожидаемый результат :

 Сумма цифр 25 = 7
  

Щелкните меня, чтобы увидеть решение

7. Напишите программу на языке C, чтобы найти НОД двух чисел с помощью рекурсии. Перейдите в редактор
Test Data:
Введите 1-й номер: 10
Введите 2-й номер: 50
Ожидаемый результат :

 НОД 10 и 50: 10 

Щелкните меня, чтобы увидеть решение

8. Напишите программу на C, чтобы получить наибольший элемент массива с помощью рекурсии. Перейдите в редактор
Test Data:
Введите количество элементов, которые будут храниться в массиве: 5
Введите 5 элементов в массив:
элемент - 0: 5
элемент - 1: 10
элемент - 2: 15
элемент - 3: 20
элемент - 4: 25
Ожидаемый результат :

 Самый большой элемент массива: 25
 

Щелкните меня, чтобы увидеть решение

9. Напишите программу на языке C, чтобы перевернуть строку с помощью рекурсии. Перейдите в редактор
Test Data:
Введите любую строку: w3resource
Ожидаемый результат :

 Перевернутая строка: ecruoser3w
 

Щелкните меня, чтобы увидеть решение

10. Напишите программу на языке C, чтобы найти факториал числа с помощью рекурсии. Перейдите в редактор
Test Data:
Введите число: 5
Ожидаемый результат :

 Факториал 5: 120
 

Щелкните меня, чтобы увидеть решение

11. Напишите программу на языке C для преобразования десятичного числа в двоичное с помощью рекурсии. Перейти в редактор
Тестовые данные:
Введите любое десятичное число: 66
Ожидаемый результат :

 Двоичное значение десятичного числа. 66 это: 1000010
 

Щелкните меня, чтобы увидеть решение

12. Напишите программу на языке C, чтобы проверять, является ли число простым или не использовать рекурсию. Перейдите в редактор
Test Data:
Введите любое положительное число: 7
Ожидаемый результат :

 Число 7 - простое число.

Щелкните меня, чтобы увидеть решение

13. Напишите программу на языке C, чтобы найти НОК двух чисел с помощью рекурсии. Перейдите в редактор
Test Data:
Введите 1-й номер для LCM: 4
Введите 2-й номер для LCM: 6
Ожидаемый результат :

 LCM 4 и 6: 12
 

Щелкните меня, чтобы увидеть решение

14. Напишите программу на языке C для печати четных или нечетных чисел в заданном диапазоне с использованием рекурсии.Перейдите в редактор
Тестовые данные:
Введите диапазон для печати, начиная с 1:10
Ожидаемый результат :

 Все четные числа от 1 до 10: 2 4 6 8 10
Все нечетные числа от 1 до 10: 1 3 5 7 9
 

Щелкните меня, чтобы увидеть решение

15. Напишите программу на языке C для умножения двух матриц с помощью рекурсии. Перейти в редактор
Тестовые данные:
Введите количество строк для первой матрицы: 2
Введите количество столбцов для первой матрицы: 1
Введите количество строк для второй матрицы: 1
Введите количество столбцов для второй матрицы : 2
Входные элементы в первой матрице:
элемент - [0], [0]: 1
элемент - [1], [0]: 2
Входные элементы во второй матрице:
элемент - [0], [ 0]: 3
элемент - [0], [1]: 4
Ожидаемый результат :

 Вот элементы первой матрицы:
                                                                                 
 1
 2
 Вот элементы второй матрицы:
                                                                                 
 3 4
 Умножение двух матриц:
                                                                                 
 3 4
 6 8
 

Щелкните меня, чтобы увидеть решение

16. Напишите программу на C, чтобы проверить, является ли данная строка палиндромом. Перейдите в редактор
Test Data:
Введите слово для проверки палиндрома: mom
Ожидаемый результат :

 Введенное слово - палиндром.
 

Щелкните меня, чтобы увидеть решение

17. Напишите программу на языке C для вычисления степени любого числа с помощью рекурсии. Перейти в редактор
Тестовые данные:
Введите базовое значение: 2
Введите значение мощности: 6
Ожидаемый результат :

 Значение 2 в степени 6: 64
 

Щелкните меня, чтобы увидеть решение

18. Напишите программу на языке C, чтобы найти последовательность града с заданным числом до 1. Перейдите в редактор
Тестовые данные:
Введите любое число (положительное), чтобы начать последовательность града: 13
Ожидаемый результат :

 Последовательность градин, начиная с 13, следующая:
 13 40 20 10 5 16 8 4 2 1
 Длина последовательности 10.

Щелкните меня, чтобы увидеть решение

19. Напишите программу на языке C для копирования одной строки в другую с помощью рекурсии. Перейдите в редактор
Test Data:
Введите строку для копирования: w3resource
Ожидаемый результат :

 Строка успешно скопирована.
                                                                                                              
 Первая строка: w3resource
 Скопированная строка: w3resource
 

Щелкните меня, чтобы увидеть решение

20. Напишите программу на языке C, чтобы найти первую заглавную букву в строке с помощью рекурсии. Перейдите в редактор
Test Data:
Введите строку, включающую одну или несколько заглавных букв: testString
Ожидаемый результат :

 Первая заглавная буква в строке testString - S.
 

Щелкните меня, чтобы увидеть решение

21. Напишите программу на языке C для двоичного поиска с использованием рекурсии. Перейдите в редактор
Test Data:
Введите количество элементов для хранения в массиве: 3
Введите 3 числа элементов в массиве в порядке возрастания:
элемент - 0: 15
элемент - 1:25
элемент - 2 : 35
Введите число для поиска: 35
Ожидаемый результат :

 Номер поиска, найденный в массиве.