Рекурсивное программированиеМатериал из Blitz Et CeteraВерсия от 04:23, 25 февраля 2008; Matt Merkulov (Обсуждение | вклад)
Предполагается, что ты уже понимаешь основные Блитзовские функции и программный поток.(Оператор If, циклы For...Next; While...Wend и т.п. )
Что такое рекурсия?Проще говоря, рекурсия - это когда функция вызывает саму себя, пока не произойдет какое-нибудь условие. С каждым новым вызовом, она будет менять один или более параметров, зависящих от их текущих значений. Ничего не понял??? Это дело проще всего объясняется простым примером : Простой пример - Функция факториалаМы будем писать функцию, которая будет возвращать факториал определенного числа. Факториал числа (n), это про произведение всех целых чисел от 1 до n. Например: Факториал 5 = 1 x 2 x 3 x 4 x 5, что равно 120. Не беспокойся сильно об этом, ведь дело не в том, ЧТО мы делаем, а КАК мы это делаем. Если мы будем писать функцию факториала по стандартному пути, то у нас получится что-то вроде этого: Print factorial(5)
Используя рекурсию, наш код будет выглядеть так: Print factorial(5)
Большой разницы между двумя видами функций нет, зато это показывает технику рекурсии. Ну и как это работает?Рекурсия просто заменила цикл For n=1 to number...Next . Если мы будем проверять, что происходит на каждом шагу, то мы увидим: возвращает значение 5 * factorial(4)
Надеюсь, Ты начинаешь понимать процесс. Чтобы разобраться со всем этим делом получше, можно проследить происходящее с зада на перед, так мы сможем узнать значения, которые получаются при каждом вызове функции и понять, как достигается конечный результат:
factorial(5) = 5 x 24 = 120, 24 - это значение, полученное из factorial(4) Бесконечность: не катит!В вышеприведенном примере ты заметил, что функция зовет себя, только если n не равно 1 и, так как n всегда уменьшается, мы знаем, что будет конечное число вызовов. Однако если не впихнуть это условие, то функция будет звать себя бесконечное число раз и Blitz скажет тебе тихим и поставленным голосом: "Stack Overflow" . Советую всегда вставлять такие условия в рекурсивные функции, чтобы они звали себя максимальное количество раз(а не бесконечное). Это показано в следующем примере: A Навороченный пример - Ковер Серпинского(Sierpinski)Мы изучили основы, пора бы забабахать что-нибудь поинтересней. Ковер Серпинского назван так в честь польского математика:  "Чё за?" - спросишь ты, но не волнуйся, мы разобьем процесс создания этого чуда на простенькие кусочки и разберем каждый из них. Схема построения ковра Серпинского.
Диаграмма внизу показывает 3 итерации. Заготовка растет экспоненциально на каждом уровне. 
Надеюсь, ты понял, как это всё получается. Позырим теперь, как оно делается: А теперь КОД! ;устанавливаем экран и высчитываем его центр
Const screenWidth = 800, screenHeight = 600 Как оно работает?Каждый раз, когда вызывается функция, рисуется новый квадрат и запрашивается 4 переменные: позиция по x&y нового квадрата, его размер (это будет размер всего ковра, если функция вызывается первый раз) и текущий порог рекурсии.
ОграниченияКак объяснялось выше, должно быть конечное число итераций рекурсивных функций, чтобы получалось то, что тебе нужно сделать. Я бы не рекомендовал ставить порог рекурсии более нескольких тысяч. Вывод?Как и у многих вещей в жизни, у рекурсии есть много преимуществ, но она не всегда является лучшим решением. Некоторые люди советуют избегать всего этого, но я считаю, что рекурсия является лучшим решением для многих проблем. В конце концов, это тебе решать - юзать рекурсию или нет. Некоторые из нас юзают, а некоторые - нет. Хорошо провести время.: Автор: Ghost Dancer (e-mail: ghost |
Журнал о программированнии на языках Blitz3D, BlitzPlus, BlitzMax
Просмотры
Личные инструменты
Blitz3D |
BlitzMax |
Друзья |
