Что такое глубина рекурсии

25. Понятие рекурсии. Глубина рекурсии. Механизм реализации рекурсий в языках программирования.

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

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

2. нет для задачи итеративного способа решения – в этом случае применяют метод полного или частичного перебора возможных вариантов решения задачи.

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

1. говорит о том, что реализация решения осуществляется на этапе рекурсивного разворачивания (спуска)

2. задача решается на этапе сворачивания рекурсий

Вызов подпрограммы; s>

3. когда часть задачи решается на этапе разворачивания, а часть – на этапе сворачивания

Рекурсия на PHP

В этой статье расскажу вам о рекурсии и о том как грамотно работать с ней на языке PHP.

PHP расшифровывается как PHP: Hypertext Preprocessor. Это смущает многих людей, потому что первое слово аббревиатуры это аббревиатура. Этот тип аббревиатуры называется рекурсивной аббревиатурой.

Перевод Google из официальной документации по PHP

Понятие рекурсии

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

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

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

Другим примером можно взять всем хорошо известное детское стихотворение:

У попа была собака, он её любил,
Она съела кусок мяса, поп её убил,
В землю закопал,
И надпись написал о том, что:

У попа была собака, он её любил,
Она съела кусок мяса, поп её убил,
В землю закопал,
И надпись написал о том, что:

…
Эта докучная сказка представляет собой пример простой рекурсии (здесь функция вызывает саму себя).

Глубина рекурсии

В связи с понятием рекурсии возникает понятие глубины рекурсии, то есть степени вложенности её отображений. Русская матрёшка, как правило, имеет 3-х и более вложенных в неё матрёшек. То есть глубина рекурсии в данном случае равна количеству вложенных матрёшек. Глубина рекурсии может быть равна бесконечности, в этом случае говорят о бесконечной рекурсии.

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

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

Опасности и подводные камни рекурсии

Рассмотрим простой пример.

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

То же самое касается и примера со сложной рекурсией.

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

Теперь вернёмся к понятию глубины рекурсии. И рассмотрим следующий пример.

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

Рекурсивные алгоритмы на PHP

Теперь мы можем приступить к исследованию алгоритмов основанных на рекурсии.

Существует множество таких алгоритмов:

• Нахождение факториала
• Вычисление последовательности Фибоначчи
• Поиск максимального элемента в массиве
• Вычисление перестановок Ханойских башен
• Рассчёт вариантов размена суммы монетами
• Рекурсивный обход дерева
• и т.д.

Рассмотрим некоторые из них.

Вычисление последовательности Фибоначчи

Следует сделать лирическое отступление, которое касается истории открытия данной последовательности…

В 1202 году Леонардо Пизанский, известный как Фибоначчи, решая задачу о размножении кроликов, пришёл к открытию рекуррентного соотношения:
Эта последовательность обладает одним замечательным свойством, а именно:
Число Фи, представляет собой золотую пропорцию, которая часто встречается в природе, выражая собой закон гармонии и красоты…

Вернёмся к нашему алгоритму. Знание рекуррентного соотношения позволяет нам с лёгкостью реализовать этот алгоритм на PHP:

С точки зрения программирования нам интересно знать насколько быстро он выполняется по сравнению с его реализацией на основе итераций, например этой:

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

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

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

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

Оказывается, что при рекурсивном вызове функций создаются копии её аргументов в стеке и следовательно дополнительные затраты на время выполнения операций копирования.
Чтобы обойти это, может быть использована парадигма Объектно-Ориентированного Программирования (ООП). К примеру мы можем создать массив внутри объекта, который будет иметь рекурсивный метод, внутри которого будет доступ к этому массиву так, что не потребуется передавать этот массив в качестве параметра для каждого вызова этого метода:

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

Рекурсия

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

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

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

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

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

Содержание

Числа Фибоначчи [ править ]

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

Проблемы рекурсии и как их решать [ править ]

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

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

1. создать глобальный массив F D <\displaystyle FD>, состоящий из нулей;
2. после вычисления числа Фибоначчи F ( n ) <\displaystyle F(n)>поместить его значение в F D [ n ] <\displaystyle FD[n]>;
3. в начале рекурсивной процедуры сделать проверку на то, что F D [ n ] = 0 <\displaystyle FD[n]=0>и, если F D [ n ] ≠ 0 <\displaystyle FD[n]\neq 0>, то вернуть F D [ n ] <\displaystyle FD[n]>в качестве результата, а иначе приступить к рекурсивному вычислению F ( n ) <\displaystyle F(n)>.

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

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

1. a = b = 1 <\displaystyle a=b=1>;
2. если n > 2 <\displaystyle n>2>, то сделать n − 2 <\displaystyle n-2>раз: c = a + b <\displaystyle c=a+b>; a = b <\displaystyle a=b>; b = c <\displaystyle b=c>;
3. вернуть ответ b <\displaystyle b>;

Особенно просто и наглядно функцию вычисления чисел Фибоначчи можно задать на языке 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;

Задача 1 [ править ]

Задача 2 [ править ]

Задача 3 [ править ]

Задача 4 [ править ]

Задача о золотой горе [ править ]

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

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

1. Каждый шаг может идти диагонально вниз направо или диагонально вниз налево.
2. Количество строк в треугольнике > 1 <\displaystyle >1>, но < 100 <\displaystyle <100>.
3. Числа в треугольнике все целые от 0 до 99 включительно.

В примере, описанном выше, это путь 7, 3, 8, 7, 5, дающий максимальную сумму 30.

Входные данные Информация о количестве строк в треугольнике это первое число в файле INPUT.TXT , далее записана информация о треугольнике построчно. Выходные данные Наибольшая сумма, записанная как целое число в файл OUTPUT.TXT . Для нашего примера это будет число 30.

В примере, описанном выше, это путь 7, 3, 8, 7, 5, дающий максимальную сумму 30.

Пример входных данных:

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

На рисунке обозначены две горки (треугольники): одна с вершиной в числе 3, другая с вершиной в числе 8. Эти горки пересекаются, и их пересечение тоже горка с вершиной в числе 1. Можно заметить, что при вычислении самого лучшего пути по рекурсивному алгоритму горка с вершиной в числе 1 будет использоваться дважды. Для горок с вершинами в нижних строчках повторных вызовов будет ещё больше. Это и есть причина медленности работы алгоритма.

Решить эту задачу за разумное время помогает динамическое программирование. Суть динамического программирования хорошо описана в книге Р. Беллмана [1] . Есть и более современные учебники  [2] , [3] , в них можно найти много интересных алгоритмов, основанных на динамическом программировании.

Задача 5 [ править ]

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

Задача «Сделай палиндром» [ править ]

Палиндром — это последовательность символов, которая слева-направо и справа-налево пишется одинаково. Например «АБА» или «АББ ББА». Дана последовательность символов. Какое минимальное количество символов нужно удалить из неё, чтобы получить палиндром?

Длина последовательности не больше 20 символов. Ограничение на время работы программы: 5 секунд.

Пример: Вход: ТИТ ЕЛЕ ЛЕТИТ . Выход: 2

Эта задача давалась на районной олимпиаде школьников Удмуртской республики в 1998 году. Рассмотрим её решение, основанное на рекурсии.

Если строка имеет вид h α t <\displaystyle > , где h <\displaystyle h>и t <\displaystyle t>символы, а α <\displaystyle \alpha >— подстрока, возможно пустая. Пусть S ( x ) <\displaystyle S(x)>— вычисляет минимальное количество символов, которые нужно убрать из строки x <\displaystyle x>, чтобы оставшаяся строка была палиндромом.

Базой рекурсии являются строки из одного символа и пустая строка — все они палиндромы по определению, и для них S = 0 <\displaystyle S=0>. Шаг рекурсии состоит из двух частей:

Алгоритм Евклида [ править ]

Даны два натуральных числа. Найти самое большое натуральное число, которое делит оба без остатка. Такое число называется наибольший общий делитель (НОД) (GCD — Greatest Common Divisor).

Пример: Вход: 18, 600 Выход: 6

Есть очень простой алгоритм: давайте перебирать все числа от минимального из заданных до 1 и проверять, делит ли очередное число оба заданных. Первое такое число и будет НОД. У этого алгоритма есть существенный недостаток — маленькая скорость работы. Например для чисел 1 000 000 001 <\displaystyle 1\,000\,000\,001>и 1 000 000 000 <\displaystyle 1\,000\,000\,000>придётся выполнить 1 000 000 000 <\displaystyle 1\,000\,000\,000>проверок. Более эффективно эту задачу решает алгоритм Евклида, основанный на двух простых свойствах GCD ⁡ ( a , b ) <\displaystyle \operatorname (a,b)> :

1. G C D ( a , K a ) = a <\displaystyle GCD(a,Ka)=a>, где K <\displaystyle K>— натуральное число;
2. Если a < b <\displaystyle a<b>, то G C D ( a , b ) = G C D ( a , b − a ) <\displaystyle GCD(a,b)=GCD(a,b-a)>.

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

Задача 6 [ править ]

Задача 7 [ править ]

При построении рекурсивной функции важно ответить на следующие вопросы:

1. Что будет базой рекурсии?
2. Что будет шагом рекурсии?
3. Почему выполнение шагов рекурсии всегда приведёт к базе?
4. Какова будет глубина рекурсии при данном значении аргументов? Глубина рекурсии — это глубина дерева рекурсивных вызовов, то есть длина максимального пути по стрелочкам из вершины до одного из элементарных (базовых) значений функции.
5. Как растёт размер дерева рекурсивных вызовов при увеличении входных данных? Будут ли повторяющиеся вызовы в этом дереве и имеет ли смысл делать рекурсию с запоминанием?

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

Задача 8 [ править ]

Есть несколько алгоритмов Евклида, основанных на различных рекуррентных соотношениях для НОД:

1. GCD ⁡ ( a , b ) = GCD ⁡ ( b , a   mod ⁡   b ) <\displaystyle \operatorname (a,b)=\operatorname (b,a\ \operatorname \ b)> ;
2. GCD ⁡ ( a , b ) = GCD ⁡ ( b , min ( | a   mod ⁡   b | , b − | a   mod ⁡   b | ) ; <\displaystyle \operatorname (a,b)=\operatorname (b,\min(|a\ \operatorname \ b|,\;b-|a\ \operatorname \ b|);>
3. GCD ⁡ ( a , b ) = < GCD ⁡ ( a , b 2 k ) , a  is odd, and  b = b ′ ⋅ 2 k , 2 k ⋅ GCD ⁡ ( a 2 k , b 2 k ) , a  and  b  are even, and  a = a ′ ⋅ 2 k , b = b ′ ⋅ 2 k , GCD ⁡ ( b , a − b ) , a  and  b  are odd, and  a > b . <\displaystyle \operatorname (a,b)=<\begin\operatorname \left(a,\;<\frac <2^>>\right),&a<\mbox< is odd, and >>b=b’\cdot 2^,\\2^\cdot \operatorname \left(<\frac <2^>>,\;<\frac <2^>>\right),&a<\mbox< and >>b<\mbox< are even, and >>a=a’\cdot 2^,\;b=b’\cdot 2^,\\\operatorname (b,\;a-b),&a<\mbox< and >>b<\mbox< are odd, and >>a>b.\end>>

Задачи для самостоятельного решения [ править ]

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

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

Задача 9 [ править ]

1. f ( a , n ) = a ⋅ f ( a , n − 1 )
2. f ( a , n ) = < f 2 ( a , n / 2 ) ,  if  n  is even, a ⋅ f ( a , n − 1 ) ,  if  n  is odd. <\displaystyle f(a,n)=<\beginf^<2>(a,n/2),&<\mbox< if >>n<\mbox< is even,>>\\a\cdot f(a,n-1),&<\mbox< if >>n<\mbox< is odd.>>\end>>

Задача 10 [ править ]

Задача 11 [ править ]

Число правильных скобочных структур длины 6 равно 5: ()()() , (())() , ()(()) , ((())) , (()()) .

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

Задача 12 [ править ]

Задача 13 [ править ]

Задача коммивояжёра [ править ]

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

Коммивояжёр (франц. commis voyageur), разъездной представитель торговой фирмы, предлагающий покупателям товары по имеющимся у него образцам, каталогам и тому подобное.

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

Задача коммивояжёра — побывать во всех городах (не менее одного раза) и при этом потратить как можно меньше денег на проезд и вернуться обратно.

Формулировка задачи

• внутри города проезд ничего не стоит;
• проезд между двумя городами напрямую стоит одинаково в оба конца;
• стоимость — целое число от 1 до 10000;
• городов не более 100.

Стоимости проезда между парами городов записаны в следующем формате:

Результат записывается в следующем формате:

Город задаётся названием без пробела. Длина названия города не более 30 символов. Программа должна реагировать на клавишу ESC. Если ESC была нажата, то в течении 10 секунд программа должна записать результат и закончить работу.

Снежинка Коха [ править ]

Снежинка Коха — это фрактальное множество точек на плоскости, которое похоже на снежинку.

Здесь приведена программа на языке PostScript. Этот код интерпрерируется программой GSView, которую можно взять на сайте http://www.ghostscript.com.

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

Программа «Снежинка Коха»

Заключение [ править ]

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

Рекурсивные алгоритмы на PHP. Часть 1. Основы рекурсии

В этой статье я расскажу о рекурсии и о том как грамотно работать с ней на языке PHP.

PHP расшифровывается как PHP: Hypertext Preprocessor. Это смущает многих людей, потому что первое слово аббревиатуры это аббревиатура. Этот тип аббревиатуры называется рекурсивной аббревиатурой.

Перевод Google из официальной документации по PHP

Понятие рекурсии

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

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

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

Другим примером можно взять всем хорошо известное детское стихотворение:

У попа была собака, он её любил,
Она съела кусок мяса, поп её убил,
В землю закопал,
И надпись написал о том, что:

У попа была собака, он её любил,
Она съела кусок мяса, поп её убил,
В землю закопал,
И надпись написал о том, что:

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

Глубина рекурсии

В связи с понятием рекурсии возникает понятие глубины рекурсии, то есть степени вложенности её отображений. Русская матрёшка, как правило, имеет 3-х и более вложенных в неё матрёшек. То есть глубина рекурсии в данном случае равна количеству вложенных матрёшек. Глубина рекурсии может быть равна бесконечности, в этом случае говорят о бесконечной рекурсии.

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

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

Похожие публикации:

1. Как удалить лишние пробелы в ворде
2. Почему бмв называют бумер
3. Тазавешский техноглайдер как получить
4. Яндекс товары как добавить