Рекурсия. Рекурсивные подпрограммы.
По известному вам правилу доступности переменных (объектов), в теле подпрограммы доступны все переменные (объекты), объявленные в самой подпрограмме, а также переменные (объекты) объявленные во всех объемлющих блоках, в том числе и имя самой подпрограммы. Исключение составляет случай, когда переменная (объект) имеет такое-же имя как и переменная в объемлющем блоке и экранирует собой глобальную переменную.
Следствием правила о доступности переменных (объектов) является возможность вызова подпрограммой самой себя.
Процедуры и функции, производящие вызов «самих себя» называют рекурсивными.
Рекурсия. Рекурсивный алгоритм.
Рекурсией называется ситуация, когда какая-то подпрограмма прямо или через другие подпрограммы вызывает себя в качестве подпрограммы. Реализуемый при этом алгоритм называется рекурсивным.
В математике очень часто встречаются последовательности чисел, в которых каждый следующий член выражается через предыдущие. В арифметической прогрессии, например, каждый следующий член равен предыдущему, увеличенному на разность прогрессии:
Формулы, выражающие очередной член последовательности через один или несколько предыдущих членов, называют рекуррентными соотношениями.
Рассмотрим для примера функцию вычисления факториала n!. Как правило ее определяют как правило произведения первых n чисел натурального ряда
Такое произведение можно легко вычислить с помощью итеративных конструкций (итерация ― это повторение), например, оператор цикла For
Procedure TForm1.Button1Click(Sender: TObject);
n:=StrToInt(Edit1.Text); // Вводим n для вычисления n!
For i:=1 to n do fact:=Fact*i;
Label1.Caption:=’Факториал ‘ +IntToStr(n)+’! =’+IntToStr(fact);
Однако существует другое определение факториала, в котором n! выражается через предыдущий (n-1)!, т.е. используется рекуррентная формула:
для любого n>0 n!=n*( n -1)!
Наличие рекуррентного соотношения позволяет использовать рекурсию. Например, программа, использующая рекурсивную функцию для вычисления факториала n! имеет следующий вид:
If i=0 then fact:=1
n := StrToInt ( n ); // Вводим n для вычисления n !
Label1.Caption:=’ Факториал ‘+IntToStr(n)+’! =’+IntToStr(fact(n));
Чтобы понять, как она работает, вспомним, что на время выполнения подпрограммы вызывающая подпрограмма приостанавливается, а в оперативной памяти выделяется место для локальных переменных и параметров, вызванной подпрограммы. Таким образом, при вызовах подпрограмм в оперативной памяти «накапливаются» приостановленные программы. При рекурсивных вызовах одной и той же функции fact происходит то же самое, т.е. при каждом новом вызове функции fact для ее локальных переменных и параметров выделяются новые ячейки памяти. по завершению работы функции эти ячейки удаляются.
Программы, в которых используются рекурсивные подпрограммы отличаются простотой, наглядностью и компактностью кода. Однако за эту простату приходится расплачиваться неэкономным использованием оперативной памяти, так как выполнение рекурсивных подпрограмм требует значительно большего размера оперативной памяти во время выполнения, чем нерекурсивных. При каждом рекурсивном вызове для локальных переменных, а также для параметров подпрограмм, которые передаются по значению, выделяются новые ячейки памяти в программном стеке.
В Delphi нет никаких ограничений на рекурсивные вызовы подпрограмм, необходимо только хорошо понимать, что каждый очередной рекурсивный вызов приводит к образованию новой копии локальных объектов подпрограммы и все эти копии, соответствующие цепочки активизированных и не завершенных рекурсивных вызовов, существуют независимо друг от друга.
Для рассмотрения различных форм рекурсивных подпрограмм введем некоторые определения, имеющие отношение к рекурсии.
Максимальное число рекурсивных вызовов подпрограммы без возвратов, которое происходит во время выполнения программы, называется глубиной рекурсии.
Текущий уровень рекурсии.
Число рекурсивных вызовов в каждый конкретный момент времени, называется текущим уровнем рекурсии.
Формы рекурсивных подпрограмм.
В общем случае любая рекурсивная подпрограмма (для примера назовем ее Rec) включает в себя некоторое множество операторов S и один или несколько операторов рекурсивного вызова P.
Главное требование к рекурсивным подпрограммам.
Главное требование к рекурсивным подпрограммам заключается в том, что вызов рекурсивной подпрограммы должен выполняться по условию, которое на каком-то уровне рекурсии станет ложным. Если условие истинно, то рекурсивный спуск продолжается. Когда оно становится ложным, то спуск заканчивается и начинается рекурсивный возврат из всех вызванных на данный момент копий рекурсивной подпрограммы.
Существует три разных формы рекурсивных подпрограмм:
1) Форма с выполнением действий до рекурсивного вызова (с выполнением действий на рекурсивном спуске).
2) Форма с выполнением действий после рекурсивного вызова (с выполнением действий на рекурсивном возврате).
3) Форма с выполнением действий как до, так и после рекурсивного вызова (с выполнением действий как на рекурсивном спуске, так и на рекурсивном возврате).
Все формы рекурсивных процедур находят применение на практике. Многие задачи, в том числе вычисление факториала, безразличны к тому, какая используется форма рекурсивной процедуры.
Рассмотренная в начале рекурсивная функция fact, выполняет вычисление факториала на возврате. Рассмотрим более подробно действия этой функции при вычислении 5!, используя трассировку программы (запись значений переменных на различных этапах выполнения программы).
В качестве примера мы использовали рекурсивную функцию вычисления факториала натурального числа. Может показаться, что составить программу для вычисления n! используя прямую формулу значительно проще, чем составить программу на основе рекуррентного соотношения. Но в подавляющем большинстве случаев это не так. В качестве второго примера рассмотрим программу для вычисления члена последовательности Фибоначчи, для которого рекуррентное соотношение
для любого n>2 F(n)=F(n-1)+F(n-2)
выглядит значительно проще, чем прямая формула
используя которую составить программу практически невозможно. Приведем функцию, благодаря которой можно быстро рассчитать эти числа:
If (i=1) or (i=2) then fib:=1
Рекурсивный вызов может быть косвенным. В этом случае подпрограмма обращается к себе опосредованно, путем вызова другой подпрограммы, в которой содержится обращение к первой, например:
Procedure A (i : Byte);
Procedure В (j : Byte) ;
Если строго следовать правилу, согласно которому каждый идентификатор перед употреблением должен быть описан, то такую программную конструкцию использовать нельзя. Чтобы такого рода вызовы стали возможны, вводится опережающее описание:
Procedure В (j : Byte); Forward;
Procedure A (i : Byte);
Как видим, опережающее описание заключается в том, что объявляется лишь заголовок процедуры в, а ее тело заменяется стандартной директивой Forward. Теперь в процедуре А можно использовать обращение к процедуре В ― ведь она уже описана, точнее, известны ее формальные параметры, и компилятор может правильным образом организовать ее вызов. Обратите внимание: тело процедуры В начинается заголовком, в котором уже не указываются описанные ранее формальные параметры.
Пример использования рекурсивной подпрограммы:
Задача: пара кроликов приносит раз в месяц приплод из двух крольчат (самца и самки), причем новорожденные крольчата через два месяца после рождения уже приносят приплод. Сколько пар кроликов появится через год, если в начале года была одна пара кроликов и в течение года кролики не умирают, а их воспроизводство не заканчивается?
Procedure recursya(i:Int64; Var kol1:Int64; Var kol2:Int64);
kol1:=1; //первоначальное количество пар кроликов
kol2:=2; //количество пар кроликов через месяц
i:=i-1; // рекурсивный спуск
Procedure TForm1.Button1Click(Sender: TObject);
recursya(12,kol1,kol2); //12 — количество месяцев
1. Что такое рекурсия?
2. Какие соотношения называют рекуррентными?
3. В чем заключаются преимущества и недостатки в использовании рекурсивных подпрограмм по сравнению с нерекурсивными?
4. Что называется глубиной рекурсии?
5. Что называется текущим уровнем рекурсии?
6. Сформулируйте основные требования к рекурсивным подпрограммам.
7. Назовите формы рекурсивных подпрограмм.
8. Что называют рекурсивным спуском и возвратом?
Рекурсия — Python: Функции
В этом уроке мы узнаем, что такое рекурсия, зачем она нужна и чем отличается рекурсия в математике и в языках программирования. Еще мы разберем условие завершения рекурсии и обсудим, какие виды рекурсии существуют.
Что такое рекурсия
Рекурсия в программировании — это возможность дать определение функции, используя в процессе саму определяемую функцию. В математике многие функции определены именно таким образом, поэтому и большинство языков программирования используют этот подход.
Это работает и в Python. Обычно в определении функции можно использовать только определения, которые дали ранее. Но есть одно исключение — функция в своем теле может вызывать себя. Выглядит это так:
def factorial(n): if n 0: return 1 return n * factorial(n - 1) Интерактивный пример: https://replit.com/@hexlet/python-functions-recursion-factorial#main.py
Эта функция вычисляет факториал числа n через умножение числа на факториал числа n — 1 .
Условие завершения рекурсии
В примере выше используется условие, которое прекращает рекурсию. Если в этой функции убрать условие, которое проверяет аргумент на неотрицательность, то первый же вызов этой функции заставит программу зациклиться — функция продолжит вызывать себя постоянно.
В определениях рекурсивных функций практически всегда есть подобное условие. Оно позволяет вычислению пойти по одной из веток:
- По рекурсивной — в этой ветке произойдет вызов себя
- По терминальной — закончит вычисление и вернет результат
Какой-то из аргументов рекурсивной функции должен обязательно убывать. В качестве убывания может быть:
- Уменьшение счетчика
- Отбрасывание головы списка при движении к его хвосту
- Вызов себя для части исходной структуры при обработке древовидных структур данных
Чтобы понять, что программа не зациклится, используют метод «пристального взгляда» и тесты. Особенно важно проверять срабатывание условия завершения рекурсии.
Переполнение стека
В большинстве программ, написанных на поддерживающих вызов функции языках, этот вызов устроен так: перед вызовом функции текущее место в программе запоминается в стеке. А когда функция возвращает результат, то соответствующий элемент стека отбрасывается.
Стек (stack) — это абстрактный тип данных, который похож на стопку монет. Монета, которую положили последней, будет снята первой. И при снятии монет порядок получается обратным порядку складывания.
В этом же стеке сохраняются значения аргументов функции, а иногда и другая служебная информация. При этом память, которая выделяется для стека при запуске программы, конечна и ограничена.
Если функция будет вызывать себя постоянно и не возвращать результат, то память в итоге закончится. Когда заканчивается память, выделенная для стека вызовов, стек переполняется.
В итоге мы не сможем посчитать факториал для достаточно больших чисел с помощью рекурсивной функции. Но сможем посчитать с помощью итеративной — написанной с использованием циклов и переменных.
Так выглядит переполнение стека при подсчете факториала:
factorial(1000) # Traceback (most recent call last): # File "", line 1, in # File "", line 4, in factorial # File "", line 4, in factorial # File "", line 4, in factorial # [Previous line repeated 995 more times] # File "", line 2, in factorial # RecursionError: maximum recursion depth exceeded in comparison Сообщение говорит, что превышена максимальная глубина рекурсии. Глубиной рекурсии называется количество последовательных вызовов себя без возврата значения. В Python максимальная длина искусственно ограничена, потому что проще считать количество вызовов, чем предсказывать окончание памяти.
Зачем нужна рекурсия
Некоторые алгоритмы реализуются проще, если использовать именно рекурсию, а не циклы. Часто такие алгоритмы работают с рекурсивными структурами данных — деревьями, «словарями словарей словарей» и подобными. При реализации таких алгоритмов нужно помнить, что память для стека конечна. При этом обычно конечны и сами обрабатываемые структуры данных, поэтому отказываться полностью от рекурсии не стоит.
Виды рекурсии
Рекурсии можно разделить на два вида по тому, как они себя вызывают:
- Прямая — когда функция вызывает себя
- Косвенная — когда одна функция внутри себя вызывает другую функцию, которая когда-то вызовет первую
Так же рекурсии можно разделить по количеству рекурсивных вызовов:
- Линейная — когда при вычислении результата функции функция вызывает себя один раз, как в примере с factorial . Уточним, что «один раз» — это не про общее количество вызовов функции в теле. Речь идет о количестве вызовов, результаты которых нужны для одного общего вычисления
- Каскадная — когда функция вызывает себя несколько раз
Рассмотрим подробнее линейную и каскадную рекурсию.
Пример линейной рекурсии
Если рекурсия в функции проверяет Гипотезу Коллатца , она считается линейной:
def collatz(n): if n == 1: return True if n % 2 == 0: return collatz(n // 2) return collatz(n * 3 + 1) Интерактивный пример: https://replit.com/@hexlet/python-functions-recursion-collatz#main.py
Здесь в теле функции есть два рекурсивных вызова, но в каждом заходе используется только один.
Еще один пример использования линейной рекурсии — обход коллекций. Для этого можно рекурсивно представить коллекцию как:
- Начало (голову)
- Остальную часть коллекции (хвост)
Дальше хвост также можно разложить на голову и новый хвост. И так до тех пор, пока не останется голова и пустой хвост:
[1, [2, 3]] -> [1, [2, [3]]] -> [1, [2, [3, []]]]
При рекурсивной обработке коллекции мы будем обходить коллекцию и дробить старый хвост на новую голову и новый хвост на каждой итерации. Так мы делаем до тех пор, пока не получим пустой хвост — то есть конец коллекции:
# Функция рекурсивно обходит список, суммируя числа из него def sum(array): # Мы можем использовать оператор упаковки для записи в хвост остальной части списка head, *tail = array if not tail: return head return head + sum(tail) Пример каскадной рекурсии
Если рекурсия в функции вычисляет очередное Число Фибоначчи , она называется каскадной:
def fibonacci(n): if n 2: return 1 return fibonacci(n - 1) + fibonacci(n - 2) Интерактивный пример: https://replit.com/@hexlet/python-functions-recursion-fibonacci#main.py
Здесь функция всегда вызывает себя два раза. Сначала будет два вызова, которые превратятся в четыре — два раза по два вызова. Затем в восемь — количество вызовов растет каскадно.
Открыть доступ
Курсы программирования для новичков и опытных разработчиков. Начните обучение бесплатно
- 130 курсов, 2000+ часов теории
- 1000 практических заданий в браузере
- 360 000 студентов
Наши выпускники работают в компаниях:
Максимальная глубина рекурсии в Python и как её увеличить
Рекурсия — это техника в программировании, при которой функция вызывает саму себя напрямую или косвенно. Она может быть очень полезной для решения определенных задач, но имеет свои ограничения. Одно из них — максимальная глубина рекурсии.
В Python предусмотрено ограничение на максимальную глубину рекурсии, чтобы предотвратить переполнение стека и последующий сбой программы. Это ограничение обычно установлено на достаточно высоком уровне (обычно порядка 1000), но иногда, для решения определенных задач, может потребоваться увеличить этот лимит.
def factorial(n): if n == 1: return 1 else: return n * factorial(n-1) print(factorial(2000))
В этом коде функция factorial рекурсивно вызывает сама себя для вычисления факториала числа. Но при попытке вычислить факториал числа больше 1000, получаем ошибку RecursionError: maximum recursion depth exceeded in comparison .
Чтобы увеличить максимальную глубину рекурсии, можно использовать функцию sys.setrecursionlimit(limit) . Эта функция устанавливает максимальную глубину рекурсии на указанное значение. Но стоит быть осторожным, увеличивая этот лимит, так как это может привести к переполнению стека и сбою программы.
import sys sys.setrecursionlimit(3000) print(factorial(2000)) # Теперь это работает
Таким образом, хотя увеличение максимальной глубины рекурсии может быть полезным, с ним следует обращаться с осторожностью. Более того, часто большие глубины рекурсии указывают на то, что задача, возможно, может быть решена более эффективным способом, не используя рекурсию.
Рекурсия
Исходный вариант статьи (В. В. Пупышев, «Рекурсия: плохо или хорошо?») опубликован в журнале «Потенциал».
Рекурсия — это жемчужина теории алгоритмов, и это первое, с чем знакомят школьников (сразу после процедур ввода и вывода данных, элементарных арифметических операций, оператора цикла и условного оператора).
Простота рекурсии обманчива. Метод рекурсии таит в себе много опасностей и сложностей, и в то же время готовит много приятных сюрпризов.
Давно известен такой математический приём, как разбиение задачи на простые шаги, каждый из которых тоже можно разложить на более мелкие шаги и так далее, пока не доберёмся до самых элементарных «шажочков».
Представим, что нужно пройти 1000 шагов. Для решения делаем один шаг, остаётся 999: задача упростилась. Сделав такое упрощение 999 раз, дойдём до самой элементарной задачи — шагнуть один раз. Конечно, этот пример слишком прост. Далее мы рассмотрим более сложные примеры, освещающие явление рекурсии как с хорошей так, и с плохой стороны.
Вы, наверное, уже заметили сходство понятий рекурсии и математической индукции. У рекурсии, как и у математической индукции, есть база — аргументы, для которых значения функции определены (элементарные задачи), и шаг рекурсии — способ сведения задачи к более простым.
Числа Фибоначчи [ править ]
Рассмотрим последовательность чисел 1 , 1 , 2 , 3 , 5 , 8 , 13 , 21 , … в которой каждое число является суммой двух предыдущих. Это числа Фибоначчи. Формальное их определение таково:
Функция F ( n ) задана рекурсивно, то есть «через себя». База — значения функции F на аргументах 1 и 2, а шаг — формула F ( n ) = F ( n − 2 ) + F ( n − 1 ) .
Современные языки программирования дают возможность программировать рекурсивные определения без особых усилий, но в таких определениях таятся опасности.
Проблемы рекурсии и как их решать [ править ]
При вычислении значения F ( 6 ) будут вызваны процедуры вычисления F ( 5 ) и F ( 4 ) . В свою очередь, для вычисления последних потребуется вычисление двух пар F ( 4 ) , F ( 3 ) и F ( 3 ) , F ( 2 ) . Можно нарисовать «дерево рекурсивных вызовов».
Можно заметить, что F ( 3 ) вычисляется три раза. Если рассмотреть вычисление F ( n ) при больших n , то повторных вычислений будет очень много. Это и есть основной недостаток рекурсии — повторные вычисления одних и тех же значений. Кроме того, с рекурсивными функциями связана одна серьезная ошибка: дерево рекурсивных вызовов может оказаться бесконечным и компьютер «зависнет». Важно, чтобы процесс сведения задачи к более простым когда-нибудь заканчивался.
Есть способ решить проблему повторных вычислений. Он очевиден — нужно запоминать найденные значения, чтобы не вычислять их каждый раз заново. Конечно, для этого придётся активно использовать память.
Например, рекурсивный алгоритм вычисления чисел Фибоначчи легко дополнить тремя «строчками»:
- создать глобальный массив F D , состоящий из нулей;
- после вычисления числа Фибоначчи F ( n ) поместить его значение в F D [ n ] ;
- в начале рекурсивной процедуры сделать проверку на то, что F D [ n ] = 0 и, если F D [ n ] ≠ 0 , то вернуть F D [ n ] в качестве результата, а иначе приступить к рекурсивному вычислению F ( n ) .
Такая рекурсия с запоминанием называется динамическим программированием сверху.
Рекурсию с запоминанием для вычисления чисел Фибоначчи мы привели просто для демонстрации идеи. Для чисел Фибоначчи есть простой «человеческий алгоритм», не использующий рекурсивные вызовы и запоминание всех вычисленных значений. Достаточно помнить два последних числа Фибоначчи, чтобы вычислить следующее. Затем предпредыдущее можно «забыть» и перейти к вычислению следующего:
Этот алгоритм линейный по n , то есть для вычисления n -го числа Фибоначчи требуется n шагов. Но здесь есть важная тонкость: число знаков в числе Фибоначчи растёт с n , соответственно, время выполнения операции сложения c = a + b тоже увеличивается. А именно, число знаков в числе Фибоначчи растёт примерно линейно (в любой системе счисления). Это следует из явной формулы:
Конечно, пока числа не выходят за пределы машинной точности (на компьютерах с 32-битной архитектурой это означает «меньше 2 32 > »), сложение выполняется за фиксированое число тактов. Но, начиная с F ( 48 ) , уже нельзя использовать элементарные 32-битные целочисленные типы и нужно использовать 64-битные или писать «свою» длинную арифметику, то есть представлять числа в виде массивов цифр в некоторой системе счисления (обычно используют систему с основанием 10000) и писать процедуры сложения таких чисел «столбиком». Например, число десятичных знаков в 1000-м числе Фибоначчи равно 209, и для сложения F ( 1001 ) = F ( 1000 ) + F ( 999 ) «столбиком» в десятичной системе счисления потребуется примерно 209 элементарных операций. Определение сложности задачи вычисления F ( n ) при больших n довольно трудная задача.
Указанный пошаговый алгоритм вычисления чисел Фибоначчи с учётом затрат на сложения длинных чисел является квадратичным по n (при увеличении n в k раз время вычисления F ( n ) увеличивается в k 2 > раз), а не линейным как многие считают. Числа Фибоначчи в принципе нельзя подсчитать быстрее, чем за линейное время, так как, чтобы вывести цифры числа Фибоначчи F ( n ) , уже требуется линейное по n время.
Особенно просто и наглядно функцию вычисления чисел Фибоначчи можно задать на языке Mathematica (см. http://www.wolfram.com):
Простое рекурсивное определение: F(n_) := F(n-1) + F(n-2); F(1) = F(2) = 1;
Рекурсивное определение с запоминанием: F[n_] := (F[n] = F[n-1] + F[n-2]); F[1] = F[2] = 1;
Если определить числа Фибоначчи первым способом, то время вычисления F [ 40 ] будет более минуты. Если же использовать второе определение, то 209-значное число F [ 1000 ] будет вычислено практически мгновенно, хотя, безусловно, и второй способ далеко не самый оптимальный.
Задача 1 [ править ]
Покажите, что в дереве рекурсивных вызовов рекурсивной функции вычисления числа Фибоначчи F ( n ) присутствует F ( n − 1 ) вызовов F ( 2 ) и F ( n − 2 ) вызовов F ( 1 ) . В частности при вычислении F ( 6 ) в дереве присутствуют 5 вызовов F ( 2 ) и 3 вызова F ( 1 ) .
Задача 2 [ править ]
Покажите, что рекурсивный алгоритм вычисления числа Фибоначчи F ( n ) требует времени пропорционального F ( n ) .
Задача 3 [ править ]
Найдите две геометрические прогрессии с различными ненулевыми значениями разности λ , удовлетворяющие соотношению b n = b n − 1 + b n − 2 =b_+b_> . Покажите, что сумма этих прогрессий также удовлетворяет этому соотношению. Представьте F ( n ) в виде суммы двух геометрических прогрессий, а именно, найдите C 1 > , C 2 > , λ 1 > , λ 2 > такие, что F ( n ) = C 1 ⋅ λ 1 n + C 2 ⋅ λ 2 n \cdot \lambda _^+C_\cdot \lambda _^> .
Задача 4 [ править ]
Напишите рекурсивную процедуру вычисления чисел Фибоначчи, основанную на рекуррентных формулах: F ( 2 n ) = 2 F ( n + 1 ) F ( n ) − F ( n ) 2 > и F ( 2 n + 1 ) = F ( n + 1 ) F ( n ) + 2 F ( n ) 2 + ( − 1 ) n +(-1)^> . Убедитесь в правильности этих формул с помощью численного эксперимента. Нарисуйте дерево рекурсивных вызовов для n = 2 10 = 1024 =1024> и n = 2 10 − 1 = 1023 -1=1023> . Как растёт размер этого дерева в зависимости от n ? Выведите формулы зависимостей F ( 2 n ) и F ( 2 n + 1 ) от F ( n ) и F ( n − 1 ) . Напишите рекурсивную функцию, использующую эти четыре формулы в зависимости от чётности n так, чтобы в дереве рекурсивных вызовов были только такие F ( m ) , для которых двоичная запись m есть левая часть двоичной записи числа n , дополненая справа нулём или единицей.
Задача о золотой горе [ править ]
На международной олимпиаде по информатике в 1994 году в первый день среди прочих задач была дана следующая задача.
Формулировка задачи: На рисунке показан пример треугольника из чисел. Написать программу, вычисляющую наибольшую сумму чисел, через которые проходит путь, начинающийся на вершине и заканчивающийся где-то на основании.
- Каждый шаг может идти диагонально вниз направо или диагонально вниз налево.
- Количество строк в треугольнике > 1 1> , но < 100 .
- Числа в треугольнике все целые от 0 до 99 включительно.
В примере, описанном выше, это путь 7, 3, 8, 7, 5, дающий максимальную сумму 30.
Входные данные Информация о количестве строк в треугольнике это первое число в файле INPUT.TXT , далее записана информация о треугольнике построчно. Выходные данные Наибольшая сумма, записанная как целое число в файл OUTPUT.TXT . Для нашего примера это будет число 30.
В примере, описанном выше, это путь 7, 3, 8, 7, 5, дающий максимальную сумму 30.
Пример входных данных:
5 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5
Эту задачу можно встретить и под названием «Золотая гора» — нужно спуститься с горы и собрать как можно больше золота.
Можно заметить, что в любом месте горы начинается гора меньшего размера, будем называть такие горы горками. Пусть число a ( i , j ) есть число в треугольнике, находящееся в i -й строчке на j -м месте, а число ( i , j ) есть максимальное значение суммы, которое можно получить спускаясь с горки, начиная с этого элемента. Понятно, что ( i , j ) есть число a ( i , j ) плюс максимум из двух вариантов: ( i + 1 , j ) и ( i + 1 , j + 1 ) . Эти два варианта соответствуют тому, что мы можем спуститься вниз-вправо или вниз-влево. Получилось рекурсивное определение: S ( i , j ) = a ( i , j ) + max ( S ( i + 1 , j ) , S ( i + 1 , j + 1 ) ) S(i+1,j),\;S(i+1,j+1)> . На основе этой рекуррентной формулы можно написать рекурсивный алгоритм. Но нужно быть осторожным. Попробуем вычислить время работы нашего алгоритма при входных данных максимального размера — 100 строк. Рекурсивный алгоритм вычисления функции S ( i , j ) перебирает все возможные пути. Сколько их? На каждом шаге есть возможность выбрать один вариант из двух (направо или налево). Количество шагов равно количеству строк треугольника. Значит, количество всех путей равно 2 100 > (Покажите, что число путей из вершины до j -го элемента i -й строчки равно биномиальному коэффициенту C i j ^> ) Это очень большое число. Столько вариантов не успеет перебрать даже самая мощная вычислительная техника. Если предположить, что машина просматривает миллиард вариантов в секунду, то понадобится 2 100 10 9 >>>> секунд. Чтобы считать было удобнее, заметим, что 2 100 10 9 = 16 25 10 9 > 10 25 / 10 9 = 10 16 >>>=>>>>10^/10^=10^> секунд, что соответствует более, чем 10 12 > часов, или более 10 000 000 лет. Понятно, что такая программа никому не нужна, её результаты узнать невозможно. За такое время все компьютеры, решающие эту задачу, превратятся в пыль.
На рисунке обозначены две горки (треугольники): одна с вершиной в числе 3, другая с вершиной в числе 8. Эти горки пересекаются, и их пересечение тоже горка с вершиной в числе 1. Можно заметить, что при вычислении самого лучшего пути по рекурсивному алгоритму горка с вершиной в числе 1 будет использоваться дважды. Для горок с вершинами в нижних строчках повторных вызовов будет ещё больше. Это и есть причина медленности работы алгоритма.
Решить эту задачу за разумное время помогает динамическое программирование. Суть динамического программирования хорошо описана в книге Р. Беллмана [1] . Есть и более современные учебники [2] , [3] , в них можно найти много интересных алгоритмов, основанных на динамическом программировании.
Общая идея динамического программирования заключается в том, что мы рассматриваем вместо одной задачи целое семейство задач. Это семейство задач у нас будет таким: найти наилучший путь из вершины ( i , j ) . Для каждой пары i , j получим одну задачу. При i = 1 и j = 1 получается исходная задача, которую нам нужно решить. Начнём решать эти задачи с простых: сначала для нижней строчки, затем второй снизу и так далее, пока не дойдём до самой верхней строчки треугольника.
По сути, идея динамического программирования заключается в запоминании вычисленных значений ( i , j ) . Их можно рассматривать как двумерный массив, элементы которого пошагово вычисляются с последней строчки, снизу — вверх.
Подсчитаем количество шагов алгоритма, основанного на динамике. Если количество строк N , то длины строк представляют собой последовательные натуральные числа 1 , 2 , … , N . Элемент массива вычисляется один раз за небольшое фиксированное количество элементарных операций по формуле ( i , j ) = a ( i , j ) + max ( S ( i + 1 , j ) , S ( i + 1 , j + 1 ) ) S(i+1,j),\;S(i+1,j+1)> . Значит время работы всего алгоритма пропорционально количеству элементов в нашем треугольнике (а в общем случае — количеству задач в семействе). Ответ равен 1 + 2 + 3 + ⋯ + N = N ( N − 1 ) 2 = Θ ( N 2 ) >=\Theta (N^)> . Символ Θ ( N 2 ) <\displaystyle \Theta (N^)> означает «примерно пропорционально N 2 <\displaystyle N^> ». Действительно, если мы N ( N − 1 ) 2 = N 2 − N 2 >=<\frac
Задача 5 [ править ]
Пусть значения чисел a ( i , j ) в треугольнике не хранятся в массиве, а быстро вычисляются некоторой внешней функцией от двух аргументов. Придумайте алгоритм, который использует память Θ ( N ) и работает время Θ ( N 2 ) )> .
Подсказка: В памяти достаточно хранить значения ( i , j ) для одной последней строчки — самой верхней из рассмотренных.
Эта задача показывает, что придумать рекурсивный алгоритм часто намного проще, чем не рекурсивный. Также несложно добавить к рекурсии запоминание вычисленных значений. Но нередко существует более быстрый алгоритм, основанный на динамическом программировании, который использует меньше памяти, нежели рекурсия с запоминанием, и делает в два раза меньше операций обращения к памяти.
Задача «Сделай палиндром» [ править ]
Палиндром — это последовательность символов, которая слева-направо и справа-налево пишется одинаково. Например «АБА» или «АББ ББА». Дана последовательность символов. Какое минимальное количество символов нужно удалить из неё, чтобы получить палиндром?
Длина последовательности не больше 20 символов. Ограничение на время работы программы: 5 секунд.
Пример: Вход: ТИТ ЕЛЕ ЛЕТИТ . Выход: 2
Эта задача давалась на районной олимпиаде школьников Удмуртской республики в 1998 году. Рассмотрим её решение, основанное на рекурсии.
Если строка имеет вид h α t > , где h и t символы, а α — подстрока, возможно пустая. Пусть S ( x ) — вычисляет минимальное количество символов, которые нужно убрать из строки x , чтобы оставшаяся строка была палиндромом.
Базой рекурсии являются строки из одного символа и пустая строка — все они палиндромы по определению, и для них S = 0 . Шаг рекурсии состоит из двух частей:
Получается, что функция S иногда три раза вызывает себя для меньших строк, чтобы затем из результатов выбрать минимальный. Легко заметить, что тут много повторных вычислений. Избавиться от них поможет запоминание значений S при различных x , которые встречались при вычислении. Однако, тут есть одна техническая проблема. Заметим, что x — это строка. Получается, нужно быстро запоминать и находить значения по заданной строке. Эту задачу решают хэш-таблицы. Но в данном случае можно обойтись и без них. Ясно, что в качестве x могут выступать лишь подстроки исходной строки, то есть некоторые кусочки подряд идущих символов из исходной строки. Каждая подстрока определяется двумя числами — номером первого символа и номером последнего.
Соответственно, получается двупараметрическое семейство задач. Задача P ( i , j ) , где j > i i> , есть поиск решения для строки, составленной из символов исходной строки с i -го по j -й символ включительно. Ответы на эти задачи естественно хранить в обычном двумерном массиве. Задачи P ( i , i ) и P ( i , i + 1 ) имеют очевидное решение S = 0 . То есть «диагональ массива» и следующая сверху «диагональ» заполнены нулями. На следующем шаге можно решить задачи вида P ( i , i + 2 ) , затем P ( i , i + 3 ) и так далее. В конце концов мы доберёмся до задачи P ( 1 , n ) , соответствующей исходной задаче ( n — длина данного слова).
Алгоритм Евклида [ править ]
Даны два натуральных числа. Найти самое большое натуральное число, которое делит оба без остатка. Такое число называется наибольший общий делитель (НОД) (GCD — Greatest Common Divisor).
Пример: Вход: 18, 600 Выход: 6
Есть очень простой алгоритм: давайте перебирать все числа от минимального из заданных до 1 и проверять, делит ли очередное число оба заданных. Первое такое число и будет НОД. У этого алгоритма есть существенный недостаток — маленькая скорость работы. Например для чисел 1 000 000 001 и 1 000 000 000 придётся выполнить 1 000 000 000 проверок. Более эффективно эту задачу решает алгоритм Евклида, основанный на двух простых свойствах GCD ( a , b ) (a,b)> :
Рассмотрим второе свойство. При замене одного из чисел на его разность с первым, наибольший общий делитель остаётся прежним.
Если после вычитания b − a получается число, большее a , операцию вычитания можно повторить. Так можно продолжать, пока разность не станет меньше a . Можно догадаться, что вместо нескольких вычитаний достаточно выполнить одну операцию деления с остатком и взять получившийся остаток. Запишем формулы, которые позволят нам определить рекурсивную функцию вычисления НОД:
Запись « a mod b \ b> » означает «остаток при делении a на b ». Здесь K — натуральное число.
Оценить количество шагов данного алгоритма достаточно сложно, но скорость его очень велика. Хватит 50 шагов этого алгоритма, чтобы найти НОД любой пары чисел, каждое из которых не превышает 2 000 000 000 . Интересно отметить, что дольше всего алгоритм работает тогда, когда данные числа есть пара соседних чисел Фибоначчи. Число шагов в алгоритме Евклида напрямую связано с длиной разложения рационального числа a b >> в цепную дробь. Разложением положительного числа x в цепную дробь называется представление x = a 0 + a 1 / ( a 2 + 1 / ( a 3 + 1 / ( a 4 + … ) ) ) +a_/(a_+1/(a_+1/(a_+\dots )))> , где числа a i > натуральные. Разложение дробей (рациональных чисел) в цепную дробь конечно. Вот примеры разложений отношений соседних чисел Фибоначчи в цепную дробь:
Задача 6 [ править ]
Докажите, что разложение в цепную дробь эквивалентно алгоритму Евклида. Докажите, что GCD ( F ( n + 1 ) , F ( n ) ) = 1 (F(n+1),\;F(n))=1> и число шагов в алгоритме Евклида для пары ( F ( n + 1 ) , F ( n ) ) F(n+1),\;F(n)> равно n . Верно ли, что F ( 50 ) > 2 000 000 000 2\,000\,000\,000> ?
Задача 7 [ править ]
Докажите, что на парах вида ( k , F ( n + 1 ) ) k,\;F(n+1)> , k = 1 , 2 , … , F ( n + 1 ) − 1 алгоритм Евклида дольше всего работает при k = F ( n ) , и число шагов алгоритма при этом равно n .
При построении рекурсивной функции важно ответить на следующие вопросы:
- Что будет базой рекурсии?
- Что будет шагом рекурсии?
- Почему выполнение шагов рекурсии всегда приведёт к базе?
- Какова будет глубина рекурсии при данном значении аргументов? Глубина рекурсии — это глубина дерева рекурсивных вызовов, то есть длина максимального пути по стрелочкам из вершины до одного из элементарных (базовых) значений функции.
- Как растёт размер дерева рекурсивных вызовов при увеличении входных данных? Будут ли повторяющиеся вызовы в этом дереве и имеет ли смысл делать рекурсию с запоминанием?
Одно из важных достоинств рекурсивных алгоритмов заключается в том, что они просты и наглядны. Но рекурсия не всегда является эффективным (самым быстрым) решением. Рекурсия использует мало памяти, но работать может довольно долго, как в примере с числами Фибоначчи.
Задача 8 [ править ]
Есть несколько алгоритмов Евклида, основанных на различных рекуррентных соотношениях для НОД:
Эффективность этих алгоритмов можно оценивать с помощью среднего числа шагов алгоритма, необходимых для вычисления GCD ( m , N ) (m,N)> , где N фиксированно, а m пробегает значения 1 , 2 , … , N − 1 . Известно, что это число примерно пропорционально log 2 N N> . Вычислите экспериментально коэффициенты пропорциональности для указанных трёх случаев. Явные выражения для этих коэффициентов довольно сложны.
Задачи для самостоятельного решения [ править ]
Существуют и другие задачи, решаемые рекурсией и динамическим программированием. Вот самые известные: обход конём шахматной доски, задача о восьми ферзях, триангуляция, поиск пути в лабиринте, вычисление арифметического выражения и многое другое.
Ниже предлагается несколько простых задач, для знакомства с идеей рекурсии.
Задача 9 [ править ]
Напишите две рекурсивные процедуры вычисления f ( a , n ) = a n > , основанные на двух различных соотношениях:
База рекурсии в обоих случаях f ( a , 0 ) = a 0 = 1 =1> . Какое получается дерево рекурсивных вызовов при n = 1000 ? Имеет ли смысл запоминать вычисленные значения? Чему равно число шагов при n = 1000 ? Какая из процедур оказалась более эффективной? Покажите, что в случае (2) число рекурсивных вызовов (число вершин в дереве рекурсивных вызовов) ограничено сверху числом 2 ( log 2 n + 1 ) n+1)> .
Задача 10 [ править ]
Найдите число различных путей из точки A в точку B по стрелочкам. Напишите программу, которая вычисляет число этих путей для таких треугольных конфигураций (графов) со стороной n .
Задача 11 [ править ]
Число правильных скобочных структур длины 6 равно 5: ()()() , (())() , ()(()) , ((())) , (()()) .
Напишите рекурсивную программу генерации всех правильных скобочных структур длины 2 n . Определение правильной скобочной структуры можно задать в нотации EBNF (в расширенной форме Бэкуса — Наура) рекурсивно:
s ::= '(' s ')' | s s | ''
Эта строчка содержит рекурсивное определение объекта s : «объект типа s может быть получен из объекта типа s с помощью окружения его открывающейся и закрывающейся круглой скобки, или с помощью приписывания двух объектов типа s друг к другу, либо это просто пустое слово». Вертикальная черта в нотации EBNF означает союз «или». С помощью одинарных кавычек выделяют символы или строки символов, пробелы играют роль разделителей.
Задача 12 [ править ]
Чему равно число c n > правильных скобочных структур длины 2 n ? Найдите рекуррентную формулу для числа c n > , а именно выразите c n > через все предыдущие c n − 1 , … , c 1 ,\dots ,c_> . Напишите программу, которая вычисляет число c n > правильных скобочных структур длины 2 n .
Подсказка: найдите перебором первые элементы последовательности c n = < 1 , 2 , 5 , … >=\> . Рассмотрите соотношения соседних элементов и догадайтесь до явной формулы.
Второй способ. Задача решается методом динамического программирования. Число различных путей из A в B по стрелкам на рисунке из задачи 10 равно числу правильных скобочных структур длины 6 (стрелка вверх соответствует открывающей скобке, а стрелка вниз — закрывающей). Придумайте способ последовательного вычисления числа различных путей из вершины A до различных вершин графа. Сколько памяти использует ваша программа для вычисления c n > в зависимости от n ?
Задача 13 [ править ]
Известный алгоритм быстрой сортировки Хоара также основан на рекурсии. Пусть нам нужно отсортировать кусочек массива A от элемента с индексом b по элемент с индексом e включительно. Перераспределим элементы на этом кусочке так, чтобы вначале стояли элементы меньшие либо равные A b > , а потом элементы большие либо равные A b > . Пусть последний элемент в первом кусочке оказался на месте c . Вызовем рекурсивно сортировку двух кусочков от b до c и от c + 1 до e включительно, (если, конечно, эти кусочки состоят более, чем из одного элемента). Воплотите эту идею в работающую процедуру сортировки массива. Проведите эксперименты по оценке средней глубины дерева рекурсии и времени работы алгоритма в зависимости от размера массива. Рассмотрите случаи а) случайного массива, б) массива, упорядоченного по возрастанию, и в) массива, упорядоченного по убыванию.
Задача коммивояжёра [ править ]
Рекурсия с запоминанием работает не всегда. Рассмотрим пример задачи, для которой есть долго работающий рекурсивный алгоритм, который нельзя существенно ускорить с помощью запоминания вычисленных значений.
Коммивояжёр (франц. commis voyageur), разъездной представитель торговой фирмы, предлагающий покупателям товары по имеющимся у него образцам, каталогам и тому подобное.
Наш коммивояжёр ездит по городам с целью сбыта товаров разного рода. Он всегда начинает и заканчивает свой путь в одном и том же городе. На проживание во всех городах коммерсант тратит одинаковую сумму денег. Поэтому существенна только сумма на проезд из города в город. Есть список городов и стоимость проезда между некоторыми парами городов.
Задача коммивояжёра — побывать во всех городах (не менее одного раза) и при этом потратить как можно меньше денег на проезд и вернуться обратно.
Формулировка задачи
- внутри города проезд ничего не стоит;
- проезд между двумя городами напрямую стоит одинаково в оба конца;
- стоимость — целое число от 1 до 10000;
- городов не более 100.
Стоимости проезда между парами городов записаны в следующем формате:
Результат записывается в следующем формате:
Город задаётся названием без пробела. Длина названия города не более 30 символов. Программа должна реагировать на клавишу ESC. Если ESC была нажата, то в течении 10 секунд программа должна записать результат и закончить работу.
Кажется, что для решения такой задачи достаточно хранить самые оптимальные промежуточные пути и вот он динамический алгоритм. Например, рассмотрим тройки городов и для каждой тройки определим в какой последовательности лучше всего её проходить. Затем рассмотрим все четвёрки городов. Решения для четвёрок можно найти на основе известных решений для троек и так далее. Но дело в том, что число возможных наборов k городов и n возможных очень быстро растёт с n и k . Например, 50 городов из 100 можно выбрать 100 891 344 545 564 193 334 812 497 256 способами. Таким образом, запоминать промежуточные решения нет никакой возможности — их слишком много даже для n = 100 , а на практике нужно решать задачи с n = 10 6 > . Для задачи коммивояжёра на плоскости можно использовать ряд эвристических идей, которые позволяют находить приемлемые решения за разумное время. Но при этом даже для случая точек на плоскости задача коммивояжёра остаётся полиномиально неразрешимой, то есть не существует алгоритма, который бы находил самый оптимальный путь коммивояжёра за время ограниченное полиномом C + n k > произвольной степени k при любой константе C .
Снежинка Коха [ править ]
Снежинка Коха — это фрактальное множество точек на плоскости, которое похоже на снежинку.
Здесь приведена программа на языке PostScript. Этот код интерпрерируется программой GSView, которую можно взять на сайте http://www.ghostscript.com.
Снежинка рисуется рекурсивным образом. Сначала она выглядит как треугольник. Затем на сторонах этого треугольника рисуются треугольные выступы. Получается шеcтиконечная звезда. На сторонах этой звезды снова рисуются треугольные выступы (см. синюю фигуру). Процесс наращивания треугольных выступов можно продолжить до бесконечности и получить в пределе вполне корректно определённое множество точек на плоскости.
В математике, в отличие от программирования, допускаются такие бесконечные рекурсивные определения. На каждом шаге у нас получается некоторая обычная фигура (не фрактал), а в пределе (после бесконечного числа шагов) получается фрактал. Если положить, что длина стороны исходного треугольника равна 1, то длина стороны шестиугольной звезды равна 1 3 >> . Длина стороны следующей фигуры ещё в три раза меньше, то есть 1 9 >> . Можно записать общую формулу: l n = 1 3 ⋅ 3 ⋯ 3 = 1 3 n =>=>>> . Заметьте, что число сторон m n > растёт от номера шага как 3 , 12 , 48 , … , то есть m n = 3 ⋅ 4 n =3\cdot 4^> . Периметр P n <\displaystyle P_> фигуры, получающейся на шаге n , есть произведение числа сторон на длину: P n = l n ⋅ m n = 3 ⋅ 4 n 3 n = 3 ( 4 3 ) n <\displaystyle P_=l_\cdot m_=3\cdot <\frac <4^>>>=3\left(>\right)^> . Таким образом, периметр фигуры растёт с каждым шагом и стремится к бесконечности.
Задача. Пусть две вершины начального правильного треугольника лежат в точках ( 0 ; 0 ) и ( 1 ; 0 ) . Какие ещё есть точки с рациональными координатами, принадлежащие снежинке Коха?
Программа «Снежинка Коха»
%!PS-Adobe /inch def /depth 6 def % глубина рекурсии /baseX 1 inch def % положение левого нижнего /baseY 5 inch def % угла исходного треугольника /edge 6 inch def % длина стороны треугольника 0.8 setlinewidth % толщина линии % buildElem - ГЛАВНАЯ РЕКУРСИВНАЯ ФУНКЦИЯ /buildElem < 2 copy /recDepth 0 def /L 0 def /L exch store % L = arg2 /recDepth exch store % recDepth = arg1 recDepth 0 le < newpath 0 0 moveto L 0 rlineto stroke > < gsave /recDepth recDepth 1 sub store /delta L 3 div def recDepth delta buildElem gsave dup 0 translate 60 rotate buildElem dup 0 translate -120 rotate buildElem grestore dup 2 mul 0 translate buildElem pop pop grestore >ifelse > def gsave baseX baseY translate 60 rotate depth edge buildElem edge 0 translate -120 rotate buildElem edge 0 translate -120 rotate buildElem pop pop grestore stroke showpage Заключение [ править ]
Рекурсивный метод решения задач является чуть ли не базовым методом решения алгоритмических задач. Рекурсия, дополненная идеями динамического программирования, жадными алгоритмами и идеей отсечения, превращается в тяжёлую артиллерию программистов. Но не следует забывать, что краткость записи рекурсивных функций не всегда означает высокую скорость их вычисления. И есть ряд задач, в которых рекурсия просто вредна (такова, например, задача вычисления кратчайшего пути в графе).
Дальнейшее чтение [ править ]
- ↑ Беллман Р. Динамическое программирование. — М.: Изд-во иностр. лит., 1960.
- ↑ Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. — М.: Мир 1979.
- ↑ Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. — М.: МЦНМО, 1999.
- Учебники, близкие к завершению
- Учебники по степени готовности/все учебники
- Информатика/все учебники
- Точные науки/все учебники
- Наука/все учебники
- Требуется внимание (все учебники)
- Учебники по теме/все учебники
- Компьютеры/все учебники
- По алфавиту/Р