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

Рекурсия — 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 студентов

Наши выпускники работают в компаниях:

Функция вызывает сама себя?

Есть несколько переменных(6) разных типов, я их всех решил вывести циклом на экран.
Но меня интересует строка, которую я пометил комментом.
Что она именно делает?
Цикл будет применять условие is array ко всем элементам массива?
И если внутри общего массива окажется еще один массив в моём случае это «$d»,
то выполнится filter($items) верно?

Но что делает этот самый filter($items)?
Я не совсем понимаю, что происходит дальше с этим filter($items).

$a = 1; $b = 1.2; $c = "xopa"; $d = [32,12]; $e = true; $f = null; function filter($massive) < foreach($massive as $items)< if (is_array($items))< filter($items); // интересует эта строка, что она делает? >else < echo $items . "
"; >> > filter([$a, $b, $c, $d, $e, $f]);

• Вопрос задан более года назад
• 134 просмотра

Комментировать
Решения вопроса 0
Ответы на вопрос 3

Это называется — рекурсия. Выполняется та же самая функция, с самой первой строчки, только аргументом к ней будет внутренний массив. Так что она выведет те два числа — 32 и 12 через отбивку и закончит работу, вернувшись в вызвавшую функцию.
Для человеческого понимания представьте, что на месте рекурсивного вывода на распечатку еще раз положили распечатку той же функции. И если надо — можно накладывать сверху еще сколько угодно листов с такими распечатками. А когда их текст заканчивается — снимать, возвращаясь на то же самое место, откуда был вызов.

Ответ написан более года назад
Нравится 1 4 комментария
Человек @xGreen_Max Автор вопроса

Внутренний массив, в моём случае это переменная $d ?
насколько я знаю, чтобы получить доступ к многомерному массиву нужен вложенный цикл, а у меня всего 1 цикл получается. Как это понимать?

Cерега Белый, так у вас первое же, что делается в вызванной функции — это цикл по внутреннему массиву. Получается, вложенный.

Человек @xGreen_Max Автор вопроса

Adamos, а если вместо filter($items); создать вложенный цикл

if(is_array($items))< foreach($items as $child)< echo "массив(вложенный в общий) - , "; >>

То этот цикл больше нагрузит память, чем вызов рекурсии filter($items); ?

Cерега Белый, нет, наоборот, вызов функции — это лишние накладные расходы. Но вызов функции позволит обработать массивы любой вложенности, а вложенный цикл — только на один уровень вглубь. Если у вас $d = [[10, 20], 32]; — рекурсия развернет каждое значение, а вложенный цикл выдаст ошибку — в echo попадет массив [10, 20] вместо значения.

Как работает рекурсия – объяснение в блок-схемах и видео

Представляю вашему вниманию перевод статьи Beau Carnes How Recursion Works — explained with flowcharts and a video.

«Для того чтобы понять рекурсию, надо сначала понять рекурсию»

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

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

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

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

Какой подход для Вас проще?

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

function look_for_key(main_box) < let pile = main_box.make_a_pile_to_look_through(); while (pile is not empty) < box = pile.grab_a_box(); for (item in box) < if (item.is_a_box()) < pile.append(item) >else if (item.is_a_key()) < console.log("found the key!") >> > >

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

function look_for_key(box) < for (item in box) < if (item.is_a_box()) < look_for_key(item); >else if (item.is_a_key()) < console.log("found the key!") >> >

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

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

Граничный и рекурсивный случай

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

// WARNING: This function contains an infinite loop! function countdown(i) < console.log(i) countdown(i - 1) >countdown(5); // This is the initial call to the function.

Эта функция будет считать до бесконечности. Так что, если Вы вдруг запустили код с бесконечным циклом, остановите его сочетанием клавиш «Ctrl-C». (Или, работая к примеру в CodePen, это можно сделать, добавив “?turn_off_js=true” в конце URL.)

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

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

function countdown(i) < console.log(i) if (i else < // recursive case countdown(i - 1) >> countdown(5); // This is the initial call to the function.

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

Сначала мы выведем цифру 5, используя команду Console.Log. Т.к. 5 не меньше или равно 1, то мы перейдем в блок else. Здесь мы снова вызовем функцию и передадим в нее цифру 4 (т.к. 5 – 1 = 4).

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

Стек вызовов

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

Я продемонстрирую Вам стек вызовов в действии, используя функцию подсчета факториала. Factorial(5) пишется как 5! и рассчитывается как 5! = 5*4*3*2*1. Вот рекурсивная функция для подсчета факториала числа:

function fact(x) < if (x == 1) < return 1; >else < return x * fact(x-1); >> 

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

Заметили, как каждое обращение к функции fact содержит свою собственную копию x. Это очень важное условие для работы рекурсии. Вы не можете получить доступ к другой копии функции от x.

Нашли уже ключ?

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

Но в рекурсивном подходе нет стопки. Так как тогда алгоритм понимает в какой коробке следует искать? Ответ: «Стопка коробок» сохраняется в стеке. Формируется стек из наполовину выполненных обращений к функции, каждое из которых содержит свой наполовину выполненный список из коробок для просмотра. Стек следит за стопкой коробок для Вас!

И так, спасибо рекурсии, Вы наконец смогли найти свой ключ и взять рубашку!

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

Заключение от автора

Надеюсь, что статья внесла немного больше ясности в Ваше понимание рекурсии в программировании. Основой для статьи послужил урок в моем новом видео курсе от Manning Publications под названием «Algorithms in Motion». И курс и статься написаны по замечательной книге «Grokking Algorithms», автором которой является Adit Bhargava, кем и были нарисованы все эти замечательные иллюстрации.

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

От себя хочу добавить, что с интересом наблюдаю за статьями и видеоуроками Beau Carnes, и надеюсь что Вам тоже понравилась статья и в особенности эти действительно замечательные иллюстрации из книги A. Bhargav «Grokking Algorithms».

• рекурсия
• алгоритмы
• обучение программированию
• образование
• javascript
• перевод

Рекурсия в JS

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

Синтаксис

function recurse() < // код функции recurse(); // функция вызывает сама себя // код функции >recurse();

Здесь функция recurse() — рекурсивная функция, поскольку вызывает сама себя в своем теле.

Как это работает

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

Как только условие выхода выполняется, функция перестает вызывать себя.

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

В общем случае это выглядит так:

function recurse() < if(условие) < recurse(); >else < // остановить вызов recurse() >> recurse();

Пример 1. Выводим числа от n до 1

function countDown(number) < // вывод в консоль console.log(number); // уменьшаем значение на один const newNumber = number - 1; // условие выхода if (newNumber >0) < countDown(newNumber); >> countDown(4);

Вывод

4 3 2 1

Как это работает

• Пользователь передает число в качестве аргумента при вызове функции. В нашем случае — 4.
• На каждой итерации значение числа уменьшается на 1.
• Функция countDown() вызывается до тех пор, пока число не станет положительным. newNumber > 0 — условие выхода из рекурсии.

Вот, как выглядят рекурсивные вызовы по шагам:

1. countDown(4) выводит 4 и вызывает countDown(3)
2. countDown(3) выводит 3 и вызывает countDown(2)
3. countDown(2) выводит 2 и вызывает countDown(1)
4. countDown(1) выводит 1 и вызывает countDown(0)
5. Текущее число — 0, поэтому newNumber > 0 = false. Выходим из рекусии.

Пример 2. Факториал с помощью рекурсии

function factorial(x) < // если число — ноль if (x === 0) < return 1; >//если число положительное else < return x * factorial(x - 1); >> const num = 3; // вызов factorial(), если число неотрицательное if (num > 0) < let result = factorial(num); console.log(`Факториал $равен $`);

Вывод

Факториал 3 равен 6

Как это работает

• Когда функция factorial() вызывается с целым положительным аргументов, она рекурсивно вызывает саму себя, уменьшая число на 1.
• Этот процесс продолжается до тех пор, пока число не станет равным 1. Когда функция в очередной раз уменьшит число на 1, оно станет равно 0. Факториал нуля — 1 → вернется единица.

Вот, как выглядят рекурсивные вызовы по шагам:

1. factorial(3) возвращает 3 * factorial(2)
2. factorial(2) возвращает 3 * 2 * factorial(1)
3. factorial(1) возвращает 3 * 2 * 1 * factorial(0)
4. factorial(0) возвращает 3 * 2 * 1 * 1