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

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

Рекурсивной (самовызываемой или самовызывающей) называют функцию, которая прямо или косвен­но вызывает сама себя.

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

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

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

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

1. При каждом вызове в функцию передавать модифицированные данные.

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

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

Пример 1. Заданы два числа a и b, большее из них разделить на меньшее, используя рекурсию.

Текст программы может быть следующим:

double proc(double, double);

puts(“ Введи значения a, b : ”);

printf(“
Результат деления : %lf”, proc(a,b));

double proc( double a, double b) <

if ( a 0, f(a)*f(b) а, и вопрос о возможности существования нескольких кор­ней на отрезке [а,b] нас не интересует. Не очень эффективная рекурсивная функция для решения поставленной задачи приведена в следующей программе:

int counter = 0; // Счетчик обращений к тестовой функции

//–––––––– Нахождение корня методом деления отрезка пополам ––––––––––

double Root(double f(double), double a, double b, double eps) <

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

Рекурсия

Важной особенностью языка JavaScript является то, что функция может вызывать не только другие функции, но и сама себя. Такие функции называются рекурсивными (recursive function). Применение рекурсивных функций, во многих случаях, позволяет писать компактный код вместо сложных вложенных циклов.

Расчет факториалов

В качестве одного из примеров можно привести расчет факториалов. Обозначается факториал восклицательным знаком "!" и вычисляется следующим образом:

Так, в соответствии с этим определением, мы имеем 5! = 5*4*3*2*1, т.е. 120 . Напомним также, что значение 0! определяется равным 1 , а факториалы отрицательных чисел не определены.

В следующем примере показано, как подсчитать факториалы итерационно, т. е. с помощью цикла while , в котором вычисляется результат:

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

Читайте также:  Первое вхождение подстроки php

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

Для того, чтобы окончательно разорвать замкнутый круг дополним рекурсивное определение N! = N * (N-1)! еще одним, которое будет служить для остановки процесса:

Попробуем теперь вычислить значение 5!, несколько раз применив правило N! = N * (N-1)! и однократно правило 1! = 1 :

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

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

А теперь давайте разберём как же работает наша функция factorial() .

Когда factorial() вызывается с аргументом 1, функция возвращает 1. В противном случае она возвращает произведение num * factorial(num — 1) . Для вычисления этого значения factorial() вызывается с num — 1. Это происходит, пока num не станет равно 1.

Например, при передаче числа 5, у нас образуется следующая цепочка вызовов:

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

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

Общее количество вложенных вызовов называют глубиной рекурсии. В случае с factorial() , всего будет num вызовов. Максимальная глубина рекурсии в браузерах ограничена 10 000 рекурсивных вызовов.

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

Определение чисел Фибоначчи

Рассмотрим другой пример – определение чисел Фибоначчи.

Числа Фибоначчи – это ряд чисел, в котором каждое последующее число равно сумме двух предыдущих: первые два числа равны 1, затем 2(1+1), затем 3(1+2), 5(2+3) и так далее 1, 1, 2, 3, 5, 8, 13 и т.д.

Читайте также:  Драйвера для планшета bamboo ctl 470

Если напрямую написать решение этой задачи, переписав рекурсию в код, то получим очень простую реализацию, повторяющую математическое определение:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Читайте также:  Amd e 450 игры

Сначала мы выведем цифру 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. Вот рекурсивная функция для подсчета факториала числа:

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

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

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

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

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

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

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

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

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

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

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

Ссылка на основную публикацию
Функции в вольфрам математика
Функции пользователя Хотя в систему входят многие сотни встроенных функций (начиная от элементарных и кончая специальными математическими функциями и системными...
Учимся рисовать в paint
Серия видео уроков «Создание компьютерного рисунка в программе Paint» МОУ «Межборская средняя общеобразовательная школа» (Уроки предназначены для детей 9-12 лет,...
Учиться без троек сканворд
Музыкант, играющий на барабанах, тарелках Передовой работник производства (ударник) Часть затвора стрелкового оружия (ударник) "Барабанщик" коммунистического труда (устар.) (ударник) "Барабанщик"...
Функция abs в паскале
Возвращает абсолютную величину параметра. Объявление Function Abs(X) : (тип параметра); Режим Windows, Real, Protected Замечания Параметр X — выражение вещественного...
Adblock detector