Рекурсия

"Чтобы понять рекурсию, нужно сперва понять рекурсию"

пример бесконечной рекурсии: Если у вас жирное пятно на платье,не переживайте. Пятна от масла убираются бензином.Пятно от бензина раствором щёлочи.Щелочь убирается эссенцией.След от эссенции потрите маслом.Hу,а как убрать пятна от масла,вы уже знаете!

Рекурсия - это процесс повторения чего-либо самоподобным способом. В программировании рекурсия - это вызов функции самой себя. Согласитесь звучит бредово? Ан нет, в рекурсиях нет ничего сверхъестественного. Главная цель при разработке рекурсии - избежать бесконечного цикла. Бесконечную рекурсию можно представить такой алгоритм: "Пройти три шага и подпрыгнуть, затем повторить тот-же алгоритм". Однако введя условие, можно избежать такого недоразумения. "Пройти три шага и подпрыгнуть, затем повторить тот-же алгоритм, если [...]". Вот тут и возникает главный вопрос "ЕСЛИ". Если сказать "повторить тот-же алгоритм, если конец асфальтированной дороги не настал", то можно получить ошибку только в одном случае, если дорога зациклена, т.е. идет по кругу, в остальных ситуациях мы можем получить успех (рано или поздно). С вступлением закончили, теперь давайте перейдем к коду.

Давайте рассмотрим рекурсию на примере нахождения факториала (n!=1*2*..*(n-1)*n). Пример №1 будет сделан с помощью цикла, а пример №2 с помощью рекурсии. Код будет написан на псевдоязыке (смесь pascal,java,c).

i:=1; result:=1; while(i<=n){result=result*i;i:=i+1;} 

Факториал, блок-схема

Суть алгоритма в умножении предыдущего результата на i, т.е. result = предыдущий результат * номер по порядку (с каждым разом он возрастает i = i + 1

function factorial(n){ if n<1 return 1; else return n*factorial(n-1); } 

Суть этого же алгоритма в углублении, до тех пор, пока n не станет равным 0, этот факт виден из постоянного уменьшения параметра n -> factorial(n-1).

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

"Это чушь - скажите вы - зачем так делать, если есть циклы?" Так вот, цель рекурсии - это не создание альтернативы циклам, а инструмент работы с деревьями и графами.

Эпилог

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

↑ Расскажите друзьям о статье


Comments system Cackle

© EduNow.su — материалы подлежат полному/частичному копированию при указании прямой ссылки на источник. (Сегодня 29.05.17)