Другими словами, рекурсия — способ общего определения объекта или действия через себя, с использованием ранее заданных частных определений. Рекурсия используется, когда можно выделить самоподобие задачи. Цитировать
Рекурсия в программировании
Функции
В программировании рекурсия — вызов функции (процедуры) из неё же самой,
непосредственно (простая рекурсия) или через другие функции (сложная рекурсия), например, функция A вызывает функцию B, а функция B — функцию A. Количество вложенных вызовов функции или процедуры называется глубиной рекурсии.
Мощь рекурсивного определения объекта в том, что такое конечное определение способно описывать бесконечно большое число объектов. С помощью рекурсивной программы же возможно описать бесконечное вычисление, причём без явных повторений частей программы.
Реализация рекурсивных вызовов функций в практически применяемых языках и средах программирования, как правило, опирается на механизм стека вызовов — адрес возврата и локальные переменные функции записываются в стек, благодаря чему каждый следующий рекурсивный вызов этой функции пользуется своим набором локальных переменных и за этот счёт работает корректно. Оборотной стороной этого довольно простого по структуре механизма является то, что рекурсивные вызовы не бесплатны — на каждый рекурсивный вызов требуется некоторое количество оперативной памяти компьютера, и при чрезмерно большой глубине рекурсии может наступить переполнение стека вызовов. Вследствие этого обычно рекомендуется избегать рекурсивных программ, которые приводят (или в некоторых условиях могут приводить) к слишком большой глубине рекурсии.
Впрочем, имеется специальный тип рекурсии, называемый «хвостовой рекурсией». Интерпретаторы и компиляторы функциональных языков программирования, поддерживающие оптимизацию кода (исходного и/или исполняемого), автоматически преобразуют хвостовую рекурсию к итерации, благодаря чему обеспечивают выполнение алгоритмов с хвостовой рекурсией в ограниченном объёме памяти. Такие рекурсивные вычисления, даже если они формально бесконечны (например, когда с помощью рекурсии организуется работа командного интерпретатора, принимающего команды пользователя), никогда не приводят к исчерпанию памяти. К сожалению, далеко не всегда стандарты языков программирования чётко определяют, каким именно условиям должна удовлетворять рекурсивная функция, чтобы транслятор гарантированно преобразовал её в итерацию. Одно из редких исключений — язык Scheme (диалект языка Lisp), описание которого содержит все необходимые сведения.
Можно отметить, что предубеждение некоторых программистов против рекурсии в значительной степени связано с традицией авторов учебников по программированию демонстрировать её использование на неподходящих примерах, типа вычисления факториала.
См. также Примеры реализации функции факториал
Данные
Описание типа данных может содержать ссылку на саму себя. Подобные структуры используются при описании списков и графов. Пример описания списка (C++):
classelement_of_list{element_of_list *next; /* ссылка на следующий элемент того же типа */intdata; /* некие данные */};
Рекурсивная структура данных зачастую обуславливает применение рекурсии для обработки этих данных.
Рекурсия в физике
Классическим примером бесконечной рекурсии являются два поставленные друг напротив друга зеркала: в них образуются два коридора из затухающих отражений зеркал. Другим примером бесконечной рекурсии является эффект самовозбуждения (положительной обратной связи) у электронных схем усиления, когда сигнал с выхода попадает на вход, усиливается, снова попадает на вход схемы и снова усиливается. Усилители, для которых такой режим работы является штатным, называются автогенераторы.
Рекурсия в лингвистике
Способность языка порождать вложенные предложения и конструкции. Базовое
предложение кошка съела мышь может быть за счет рекурсии расширено как Ваня догадался, что кошка съела мышь, далее как Катя знает, что Ваня догадался, что кошка съела мышь и так далее. Рекурсия считается одной из лингвистических универсалий, то есть свойственна любому естественному языку (хотя в последнее время активно обсуждается возможное отсутствие рекурсии в одном из языков Амазонии — пираха, которое отмечает лингвист Д. Эверетт). О рекурсии в лингвистике, ее разновидностях и наиболее характерных проявлениях в русском языке описано в статье Е.А.Лодатко "Рекурсивные лингвистические структуры" (см.: Рекурсивные лингвистические структуры)
Цитаты. Итерация от человека. Рекурсия — от Бога. — Л. Питер Дойч[1]
Юмор. Большая часть всех шуток о рекурсии касается бесконечной рекурсии, в которой нет условия выхода. Известное высказывание: Чтобы понять рекурсию, нужно сначала понять рекурсию' или 'Чтобы что-то сделать, надо что-то сделать. Весьма популярна шутка о рекурсии, напоминающая словарную статью: рекурсия
см. рекурсия
Несколько рассказов Станислава Лема посвящены (возможным) казусам при бесконечной рекурсии:
Рассказ про Йона Тихого «Путешествие четырнадцатое» из «Звёздных дневников Ийона Тихого», в котором герой последовательно переходит от статьи о сепульках к статье о сепуляции, оттуда к статье о сепулькариях, в которой снова стоит отсылка к статье «сепульки».
Рассказ о разумной машине, которая обладала достаточным умом и ленью, чтобы для решения поставленной задачи построить себе подобную, и поручить решение ей (итогом стала бесконечная рекурсия, когда каждая новая машина строила себе подобную и передавала задание ей).
Русская народная сказка-песня «У попа была собака…» являет пример рекурсии:
У попа была собака, он её любил,
Она съела кусок мяса, он её убил,
В землю закопал,
Надпись написал:
"У попа была собака, он её любил,
Она съела кусок мяса, он её убил,
В землю закопал,
Надпись написал:
"У попа была собака, он её любил,
Она съела кусок мяса, он её убил,
В землю закопал,
Надпись написал: …
Арайя
продолжай!
Soledat
Здесь как-то краешком проглядывает мысль о сетевой организации мира. Поправьте, если я не права.
U-Genius
В свое время я очень интересовался Фракталами и много читал об этом, включая и труды самого Мандельброта. В частности весь этот интерес пошел от желания объяснить и понять фрактальность финансовых инструментов. Особых успехов не добился, но появилось хоть какое-то понятие о фрактальности.
При всех уже здесь приведенных определениях и свойствах, предлагаю теперь
наиболее лаконично и по сути выразить что такое фрактал и его основные
свойства, так чтобы было понятно Тухлому ;-)
Шаоран
U-Genius: далеко не все было рассмотрено. Пролистал все тут выложенное, сделал кое какую обработку, проходим по ссылке и продолжаем работать.
http://dreamhackers.ru/index.php/topic,3863.0.html
P.S. U-Genius судя по всему нам с тобой очень повезло! Раз ты "очень интересовался Фракталами", то будь любезен "наиболее лаконично и по сути выразить что такое фрактал и его основные свойства", потому что в отличие от тебя меня они раньше не интересовали. И при всем уважении хочу тебе сказать что простого предложения мало, хотелось бы услышать твои мысли, рассуждения, увидеть тебя в роботе.
UGor
Перенес свой месаг в новую темку http://dreamhackers.ru/index.php/topic,3863.0.html
wen
Но мы ведь помним отчего плясали...оп-ля-ля...оп-ля-ля...плясали то мы от фракталов. А теперь ход конем: меняем понятие "атом", понятием "человек"! ЧеловеФокус удался!
Посмотрим на человека-кокон. Он состоит из ядра("шар осознания"), который в свою очередь из облака более мелких частиц собственно осознание и внутренних эманаций. Вокруг человека плещется море эманаций орлика. Напряжение возникающее вследствии их непосредственной близости определяет заряд(!) человека. Чем больше у человека заряд (интересный факт, что количество нейтронов и протонов у атома одинаковое, то есть увеличивается пропорционально) тем ближе он к тому чтобы обрести способность свободно перемещаться по мирам (которых у КК пока 8, а почему не сложно понять). Обретя способности он может менять свою конфигурацию, и становится существом следующей конфигурации, получая все плюсы и минусы такой конфигурации. А дойдя до последнего уровня конфигурации (миров восприятия) он увидит, что там предел. По этому нужно держаться корней, то есть первой группы т.к. она ведет к корню дерева...оп-ля-ля...оп-ля-ля...
wen
Поправка: эманации орла не только снаружи, но и пронизывают нас. То есть мы в океане.
sashas
Ребят, берёте еще в команду?
а то пропустил начало.
