Как сделать рекурсию

Обновлено: 07.07.2024

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

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

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

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

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

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

@typemoon, вы говорите, что от программирования переходите к математическому описанию. Рекурсия это тоже самое, что и принцип математической индукции. Один в один.

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

3 ответа 3

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

Например, пусть у нас есть следующая задача: нужно найти число возможных способов размена 100 рублей монетами 10 рублей, 5 рублей, 2 рубля и 1 рубль.

То есть нам надо написать функцию f(сумма, набор_монет), которую мы сможем вызвать так: result = f(100, [10, 5, 2, 1]). Первый аргумент - сумма, которую нам надо разменять, а второй - список из уникальных монет, с помощью которых можно представить эту сумму.

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

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

Сумма этих вариантов будет равна искомому числу. Тогда реализацию функции f можно записать как сумму рекурсивных вызовов самой себя с "укороченными" аргументами: f(90, [1, 2, 5, 10]) + f(100, [1, 2, 5]).

f(90, [1, 2, 5, 10]) - мы как бы "забрали" десятирублёвую монету из 100, но не ограничиваем дальнейший выбор монет;

f(100, [1, 2, 5]) - мы ничего не забрали из суммы, но ограничили набор монет.

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

Остаётся добавить граничные условия, чтобы функция не вызывалась бесконечно. Для этого нужно определить, при каких аргументах возвращать 1, а при каких - 0.

В видео есть неточность: в формуле вычисления факториала и в коде, который на ней основан, не учитывается, что для 0 (нуля) тоже можно вычислить факториал — он равен 1 (единице). Исправленный код есть ниже в конспекте.

Подготовка (Code Basics)

Если вы начинаете изучать программирование с нуля, то рекомендуем сначала пройти подготовительный курс JavaScript на нашем образовательном ресурсе Code Basics. После чего возвращайтесь сюда.

Транскрипт урока

У нас уже есть функция surfaceAreaCalculator , которая принимает один аргумент — радиус — и возвращает площадь поверхности соответствующей сферы, используя формулу 4 * pi * r 2. Помните, мы можем представить функции ящиками: кладём что-то в ящик, она производит какие-то действия и выплёвывает результат.

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

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

Ещё польза в том, что теперь код проще понять. Сравните это:

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

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

Вместо умножения радиуса на радиус, мы вызовем функцию вычисления квадрата и передадим ей радиус. Очевидно — всё, что делает функция вычисления квадрата, это "принимает число и возвращает его квадрат";

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

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

square хочет умножить num на num и сделать возврат. Ей никто не мешает и она делает это умножение и возврат. Мы снова внутри surfaceAreaCalculator , который в прямом смысле ждал, пока функция square закончит своё дело. И теперь у нас есть результат вызова square . Он заменяет вызов, поэтому теперь становится возможным завершить умножение и вернуть ответ.

Ответ возвращается и сохраняется в surfaceOfMars .

Так что функции могут вызывать другие функции. Функция не знает и не напрягается по поводу того, что она была вызвана другой функцией. Возможно, она была вызвана другой функцией, которая так же была вызвана ещё какой-то функцией! Не так важно, при условии, что вычисление возвращается и заканчивает свою работу.

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

Получается шесть уникальных комбинаций из трёх книг. Из четырёх — 24 комбинации. Из 13 — почти столько же сколько людей на планете. 25 книг? Вариантов их перестановки больше, чем атомов во Вселенной.

Вообще, существует n! вариантов перестановки n книг. Факториал означает — умножить все числа от 1 до n. Так что, 3! это 1 * 2 * 3. Давайте напишем функцию факториала.

Ой, подождите. Мы не знаем значение n изначально, в этом вся проблема. Хмм… Как там делается в математике?

А, хорошо, у них там есть два варианта: если n равно 0, тогда факториал — 1, это просто. Но если n не равно 0, тогда факториал — n*(n-1)!

Давайте попробуем вот так:

Это может показаться странным. Мы вызываем функцию из функции, но… это та же самая функция!

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

Давайте это отследим: мы вызываем factorial(3) . 3 это не 0, поэтому первое условие игнорируется. Функция хочет произвести умножение чисел и вернуть ответ, но она не может — ей нужно знать второе число, для чего она вызывает factorial(3-1) или factorial(2) .

Формируется новый идентичный ящик factorial , он принимает число 2, это не 0, так что он пробует произвести умножение и вернуть ответ, но не может — ему нужно знать второе число, поэтому он вызывает factorial(1) .

Формируется новый идентичный ящик factorial , он принимает число 1 и это снова не 0. Еще одна попытка произвести умножение и вернуть результат, происходит вызов factorial(0) и этот ящик уже может мгновенно вернуть ответ — он возвращает 1.

1 возвращается в предыдущий ящик, умножается на 2 и ответ "2" возвращается в предыдущий ящик, умножается на 3 и ответ "6" возвращается во внешний мир и сохраняется в константе answer .

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

  1. Простой базовый случай или терминальный сценарий. Это точка, в которой нужно остановиться. В нашем примере это 0: мы остановили вычисление факториала когда в функцию был передан 0.
  2. Правило передвижения по рекурсии, углубление. В нашем случае это было n * factorial(n-1) .

Ещё один момент. Если проверить наш код с помощью линтера, то он выдаст ошибку no-else-return . Последуем рекомендациями линтера и отрефакторим код:

Давайте проследим шаги ещё раз, но с другой точки зрения, не заглядывая в ящики. Вот как это выглядит пошагово:

Умножение не происходит пока мы спускаемся до базового случая функции factorial(0) . А затем мы возвращаемся наверх, производя одно умножение за один шаг.

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

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

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

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

Выводы

О функциях

  • Можно представить функции как чёрные коробки: коробка забирает объект, производит внутри какие-то действия, а потом выплёвывает что-то новое
    • Некоторые функции ничего не забирают (не принимают аргументы), некоторые вообще ничего не делают (они пустые), некоторые не возвращают значения.
    • Наш surfaceAreaCalculator принимает один аргумент (radius), вычисляет площадь поверхности и возвращает результат этого вычисления.
    • такой код легче понимать
    • функции могут переиспользоваться несколько раз

    Две функции вместе:

    Функции, которые вызывают сами себя

    • Определение функции — это описание коробки
    • Оригинал коробки формируется при вызове функции
    • Когда функция вызывает сама себя, создаётся новая идентичная коробка
    • Количество способов перестановки n объектов равно n! (перестановки)
    • n! определяется таким способом: если n = 0, то n! = 1; если n > 0, то n! = n * (n-1)!

    Функция, вычисляющая факториал:

    Требования рекурсии

    1. Простой базовый случай, или терминальный сценарий, или терминальное условие. Простыми словами, когда остановиться. В нашем примере это был 0: мы остановили вычисление факториала, когда достигли 0.
    2. Правило двигаться по рекурсии, углубляться. В нашем случае, это было n * factorial(n-1) .

    Ожидание умножения

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

    Примечание

    Заметьте, что 0! это 1, а простой базовый случай для n! это 0! В этом уроке мы пропустили такой случай, чтобы сократить рекурсию на один вызов и на одну коробку, поскольку 1 * 1 — это, в любом случае — 1.

    Просто ради забавы

    У программистов есть одна шутка: "Чтобы понять рекурсию, нужно понять рекурсию". Google, кажется, любит такие шутки. Попробуйте погуглить "рекурсия" и зацените верхний результат поиска ;-)

    Дополнительные материалы

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

    Нашли опечатку или неточность?

    Выделите текст, нажмите ctrl + enter и отправьте его нам. В течение нескольких дней мы исправим ошибку или улучшим формулировку.

    Что-то не получается или материал кажется сложным?
    • задайте вопрос. Вы быстрее справитесь с трудностями и прокачаете навык постановки правильных вопросов, что пригодится и в учёбе, и в работе программистом;
    • расскажите о своих впечатлениях. Если курс слишком сложный, подробный отзыв поможет нам сделать его лучше;
    • изучите вопросы других учеников и ответы на них. Это база знаний, которой можно и нужно пользоваться.
    Об обучении на Хекслете

    Открыть доступ

    Курсы программирования для новичков и опытных разработчиков. Начните обучение бесплатно.

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

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

    Для рекурсии в её наиболее общей, неитеративной форме типична необходимость отсрочки некоторых действий; см., в частности, пример (4). По этой причине она вряд ли показана для забывчивых людей, но вполне пригодна для подходящим образом оборудованных машин. Повторение же — это в значительной степени наш повседневный опыт. см. 3, 4, 6. Бауэр Гооз

    3.2. Примеры

    Пример 1. Вспомним определение натуральных чисел. Оно состоит из двух частей:

    1. 1 — натуральное число;

    2. если n — натуральное число, то n + 1 — тоже натуральное число.

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

    Пример 2 . Похожим образом задаются числа Фибоначчи: первые два числа равны 1, а каждое из следующих чисел равно сумме двух предыдущих:

    Пример 3. Популярные примеры рекурсивных объектов — фракталы. Так в математике называют геометрические фигуры, обладающие самоподобием. Это значит, что они составлены из фигур меньшего размера, каждая из которых подобна целой фигуре. На рисунке 8.2 показан треугольник Серпинского — один из первых фракталов, который предложил в 1915 г. польский математик В. Серпинский. Рис. 8.2


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

    Пример 4. Ханойские башни.

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


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

    Пусть нужно перенести n дисков со стержня 1 на стержень 3. Представим себе, что мы как-то смогли переместить n – 1 дисков на вспомогательный стержень 2. Тогда остается перенести самый большой диск на стержень 3, а затем n — 1 меньших дисков со вспомогательного стержня 2 на стержень 3, и задача будет решена. Получается такой псевдокод:

    перенести ( n -1, 1, 2)

    перенести ( n -1, 2, 3)

    Процедура перенести (которую нам предстоит написать) принимает три параметра: число дисков, начальный и конечный стержни. Таким образом, мы свели задачу переноса n дисков к двум задача переноса n – 1 дисков и одному элементарному действию — переносу 1 диска. Заметим, что при известных номерах начального и конечного стержней легко рассчитать номер вспомогательного, так как сумма номеров равна 1 + 2 + 3 = 6. Получается такая (пока не совсем верная) процедура:

    алг Hanoi (цел п, к, m )

    р:=6-к-т Hanoi ( n -1, k , p )

    вывод k , ' -> ', m , нс

    Hanoi ( n -1, p , m )

    Эта процедура вызывает сама себя, но с другими значениями параметров. Такая процедура называется рекурсивной.

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

    Основная программа для решения задачи, например, с четырьмя дисками будет содержать всего одну строку (перенести 4 диска со стержня 1 на стержень 3):

    Очевидно, что если нужно переложить 0 дисков, задача уже решена, ничего перекладывать не надо. Это и есть условие окончания рекурсии: если значение параметра п, переданное процедуре, равно 0, нужно выйти из процедуры без каких-либо действий. Для этого в школьном алгоритмическом языке используется оператор выход (в Паскале — оператор exit ). Правильная версия процедуры выглядит так:

    алг Hanoi (цел n , к, m )

    если п=0 то выход

    procedure Hanoi (n,k,m:integer);

    if n=0 then exit;

    Чтобы переложить N дисков, нужно выполнить 2 N — 1 перекладываний. Для N = 64 это число равно 18 446 744 073 709 551 615. Если бы монахи, работая день и ночь, каждую секунду перемещали один диск, им бы потребовалось 580 миллиардов лет.

    Стандартный алгоритм перевода числа в двоичную систему можно записать, например, так:

    нц пока п<>0

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

    Однако можно применить красивый подход, использующий рекурсию. Идея такова: чтобы вывести двоичную запись числа n , нужно сначала вывести двоичную запись числа div ( n , 2), а затем последнюю цифру — mod ( n , 2). Если число-параметр равно нулю, нужно выйти из процедуры.

    Такой алгоритм очень просто программируется:

    алг printBin (цел n )

    если п=0 то выход все

    procedure printBin(n:integer);

    if n=0 then exit;

    printBin(n div 2);

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

    Пример 6 . Составим функцию, которая вычисляет сумму цифр числа. Будем рассуждать так: сумма цифр числа n равна значению последней цифры плюс сумма цифр числа div ( n , 10) . Сумма цифр однозначного числа равна самому этому числу, это условие окончания рекурсии. Получаем следующую функцию:

    алг цел sumDig( цел n)

    знач:= знач + sumDig ( div ( n ,10))

    var sum: integer;

    sum:=sum+sumDig (n div 10);

    Пример 7 . Алгоритм Евклида, один из древнейших известных алгоритмов, предназначен для поиска наибольшего общего делителя (НОД) двух натуральных чисел. Формулируется он так.

    Алгоритм Евклида. Чтобы найти НОД двух натуральных чисел, нужно вычитать из большего числа меньшее до тех пор, пока меньшее не станет равно нулю. Тогда второе число и есть НОД исходных чисел.

    Этот алгоритм может быть сформулирован в рекурсивном виде. Во-первых, в нём для перехода к следующему шагу используется равенство НОД( a , b ) = НОД(а – b , b ) при а ³ b . Кроме того, задано условие останова: если одно из чисел равно нулю, то НОД совпадает со вторым числом. Поэтому можно написать такую рекурсивную функцию:

    алг цел NOD( цел a, b)

    если а=0 или b =0 то

    иначе знач :=N0D(a, b-a)

    function NOD(a, b:integer):integer

    if (a=0) or (b=0) then begin

    else NOD:=NOD(a, b-a)

    Заметим, что при равенстве одного из чисел нулю второе число совпадает с суммой двух чисел, поэтому в качестве результата функции принимается а + b .

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

    Рассмотрим ещё несколько алгоритмов, которые можно реализовать с помощью рекурсии:

    1. Алгоритм сложения двух положительных десятичных чисел.

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

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

    2. Алгоритмы разложения натурального числа на простые множители.

    Если в нашем распоряжении имеется достаточно длинная таблица простых чисел, то можно пытаться последовательно делить заданное число на 2, 3, 5, 7, . — не разделится ли без остатка,— пока, наконец, не придём к 1.

    Если же таблицы простых чисел в распоряжении нет, то можно также последовательно пытаться делить заданное число на натуральные числа 2, 3, 4, 5, 6, 7. до тех пор, пока не останется 1; при этом для каждого составного числа как делителя выполняемая попытка деления будет бесполезной.

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

    В данном случае количество элементарных тактов обработки зависит от величины разлагаемого числа.

    3. Алгоритм вставки карточки в (упорядоченную) картотеку (предполагается, что в картотеке нет рейтера – зажима для удобства отыскания картотечных карточек).

    В данном случае количество элементарных тактов обработки зависит от размера картотеки

    4. Алгоритм сортировки (несортированной) картотеки.

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

    Этот пример демонстрирует иерархическую структуру: алгоритм сортировки основан на алгоритме смешивания.

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

    5. Алгоритм вычисления значения дроби (а + b )/(а — b ).

    Сначала вычисляем (используя алгоритмы сложения и вычитания) значения выражений а + b и а — b (все равно, последовательно или одновременно, поскольку ситуация здесь совместная), а потом образуем частное от деления полученных результатов (используя алгоритм деления).

    В случае общих формул обнаруживается как иерархическое строение, так и совместность.

    В данном случае количество элементарных тактов обработки бесконечно.

    6. Алгоритм, распознающий, можно ли получить последовательность знаков а из последовательности знаков b посредством вычёркивания некоторых знаков.

    7. Алгоритм вычисления числа е (т. е. вычисления последовательности дробей — приближений для е).

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

    и образовать последовательность рациональных чисел ( Ai + В i )/(А i -В i ). C 71

    Здесь речь идёт о незавершающемся алгоритме для вычисления вычислимого вещественного числа, опирающемся на алгоритм из пункта 5.

    В примерах 3 и 4 наличие рекурсии очевидно из самого словесного описания алгоритма.

    В примере 7 речь идёт о безусловном (не зависящем от выполнения какого-либо условия) повторении.

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

    Рассмотрим вычисление факториала N!: так называют произведение всех натуральных чисел от 1 до заданного числа N : N != 1 • 2 • 3 • . • N. Факториал может быть также введён с помощью рекуррентной формулы, которая связывает факториал данного числа с факториалом предыдущего 1 ( 1 -в математике принято, что факториал нуля равен 1. Поэтому равенство 0! = 1 можно тоже принять за базовый случай):

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

    алг цел Fact (цел N )

    вывод '–> N =', N , нс

    иначе знач:= N * Fact ( N -1)

    вывод ' N =', N , нс

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

    Стек (англ. stack — кипа, стопка) — особая область памяти, в которой хранятся локальные переменные и адреса возврата из процедур и функций.

    Один из регистров процессора называется указателем стека (англ. stack pointer , SP ) — в нём записан адрес последней занятой ячейки стека. При вызове процедуры в стек помещаются значения всех её параметров, адрес возврата и выделяется место под локальные переменные.

    На рисунке 8.4, а показано начальное состояние стека, серым цветом выделены занятые ячейки. Когда функция Fact вызывается из основной программы с параметром 3, в стек записывается значение параметра, затем — адрес возврата А, и выделяется место для локальной переменной знач , в которую будет записан результат 1 ( 1 – результат функции, как правило, передаётся в вызывающую программу через регистры, но во время работы функции хранится в стеке.) (рис. 8.4, б). При втором и третьем вложенных вызовах в стек добавляются аналогичные блоки данных (рис. 8.4, в и г). Заметьте, что в нашем случае адрес возврата AF (точка внутри функции Fact после рекурсивного вызова) в последних двух блоках будет один и тот же.

    Когда выполняется возврат из процедуры, состояние стека изменяется в обратную сторону: г — в — б — а.

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

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

    Всегда ли можно написать нерекурсивную программу? Оказывается, всегда. Доказано, что любой рекурсивный алгоритм может быть записан без использования рекурсии. Хотя:

    ¾ часто при этом программа усложняется и становится менее понятной;

    ¾ нерекурсивная версия нередко требует дополнительного расхода памяти.

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

    нц для i от 1 до N

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

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

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

    Простыми словами о рекурсии

    В программировании рекурсия, или же рекурсивная функция — это такая функция, которая вызывает саму себя.

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

    Не приведёт ли рекурсивная функция к бесконечному циклу?

    Да, такой исход вполне возможен. Однако, как и у функции for или while , рекурсию можно прервать условием break , чтобы функция перестала вызывать саму себя.

    Вот пример кода того, как можно реализовать функцию обратного отсчёта с использованием рекурсии:

    Как прервать рекурсию:

    Допустим, у нас имеется функция CountDown , которая принимает аргумент (n) . Чтобы реализовать обратный отсчёт, нам следует повторить последовательность действий, понижающих значение параметра. Создадим условие вида:

    Если (n) больше 1 , то вызвать функцию CountDown и вернуться в начало цикла, затем вычесть единицу и снова проверить, выполняется ли условие (n) > 1 .

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

    Проще говоря, рекурсия делает то же, что и код ниже:

    Плюсы и минусы рекурсивных функций

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

    Плюсы:

    • Рекурсивный код снижает время выполнения функции.

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

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

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

    Многие согласятся, что эта причина очень важна. Рекурсия проста в отладке из-за того, что она не содержит сложных и длинных конструкций.

    Минусы:

    • Рекурсивные функции занимают много места.

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

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

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

    Стоит ли использовать рекурсии вместо обычных циклов?

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

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

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

    Читайте также: