Дроздовский Михаил
Рекурсия
— это обращение функции к самой себе.
Многие
не понимают, как же использовать рекурсию на практике — мол, "что за бред,
функция обращается сама к себе...
Этого не должно быть!". Действительно, кажется странновато и неудобно. Ну
что же, разберем реальный случай.
Допустим,
нам необходимо выстроить дерево записей из базы данных, каждый из которых имеет
следующие параметры:
| uid | имя записи | uid родительской записи |
Вроде,
все просто — сделал код типа
$s = mysql_query("SELECT * FROM x_table WHERE
parent_id=0", $conn);
while ($z = mysql_fetch_array($s)) {
...
$x = mysql_query("SELECT * FROM x_table WHERE
parent_id=".$z["uid"], $conn);
while ($f = mysql_fetch_array($x)) {
...
и
т.д.
}
}
Но
ведь количество уровней вложенности может быть неограниченным! Получается,
количество циклов будет бесконечным, длина кода будет бесконечной итп. Т.е.
сделать ничего не получится. Как же быть.
Некоторые
программисты просидят над этой задачей довольно долго. Конечно, можно сделать
100 циклов, в надежде, что такой глубокой вложенности записей не будет. А если
будет? К тому же код с 100 циклами будет плохочитаемым, длинным и очень
объемным. Ну а если там появится небольшая ошибка... (дальше, я думаю,
объяснять не стоит).
-------------------------
Эту
задачу достаточно легко решить с помощью рекурсии. Пишем небольшую функцию:
function tree($uid, $conn) {
$sql = "SELECT * FROM x_table WHERE parent_id=$uid";
$a = mysql_query($sql, $conn);
while($x = mysql_fetch_array($a)) {
....
какие-то действия...
tree($x["uid"], $conn);
}
}
И
запускаем ее: tree(0, $conn). Все. Сложная на вид задача решена.
Эпилог: с подобной задачей автор столкнулся при
написании одного веб-приложения на PHP.
Список литературы
Для
подготовки данной работы были использованы материалы с сайта progcpp.narod/
Другие работы по теме:
Финансовые функции и рекурсия
Вычисление значений финансовых функций с помощью электронных таблиц Excel или других прикладных программ. Рекурсивные методы решения прикладных задач, ориентированных на экономические специальности. Динамика вклада, дисконтирование, консолидирование.
Теорема о неподвижной точке
Теорема Клини о неподвижной точке - инструмент исследования в теории рекурсивных функций, способ доказательства с помощью языка с дополнительной процедурой "получить текст программы"; классический пример применения теоремы в языке программирования.
Полурешетки m-степеней
Вопросы сводимости функций. Символы логических операций: отрицания, конъюнкции, дизъюнкции, импликации. Кванторы общности и существования. Минимальные элементы верхней полурешетки m-степеней. Идеалы полурешетки m-степеней частично рекурсивных функций.
Возникновение и развитие символической логики
Возникновение и развитие символической логики связано с работами Г.Фреге (1848–1925) и Ч.С.Пирса (1839–1914). После того, как Фреге в 1879 и Пирс в 1885 ввели в язык алгебры логики предикаты, предметные переменные и кванторы, возникла реальная возможность построения системы логики в виде логического исчисления, что и было сделано Фреге, который по праву считается основателем символической логики в ее современном понимании.
Рекурсия
Содержание Рекурсия . . . . . . . . . . . . . . . . . . . . . . . . . . Пример 1 . . . . . . . . . . . . . . . . . . . . . . . . . . Пример 2 . . . . . . . . . . . . . . . . . . . . . . . . . . Пример 3 . . . . . . . . . . . . . . . . . . . . . . . . . .
Трансляторы с Алгола-60
Только в конце 50-х у пользователей советских ЭВМ появилась возможность вводить в свои машины символьную информацию. На начальных этапах все программирование было численным, поскольку устройства ввода могли работать только с числовыми данными.
Алгоритм и его свойства
Понятие алгоритма как фундаментальное понятие информатики. Алгоритмизация является набором определенных практических приемов, особых специфических навыков рационального мышления в рамках языковых средств. Человек - исполнитель алгоритма. Свойства алгоритм
Рекурсия
Рекурсия — это такой способ организации вспомогательного алгоритма (подпрограммы), при котором эта подпрограмма (процедура или функция) в ходе выполнения ее операторов обращается сама к себе.
Динамические структуры данных
Создание стека как линейного списка. Использование аналогичного ссылочного типа для организации очереди. Циклически связанный список. Построение сложных структур в динамической памяти. Бинарные (двоичные) деревья. Экран результата и контрольные расчеты.
Алгоритм нисходящего разбора. Нисходящие распознаватели
1. Задача разбора Разбор сентенциальной формы означает построение вывода и, возможно синтаксического дерева для нее. Программу разбора называют также распознавателем, так как она распознает только предложения рассматриваемой грамматики. Именно это и является нашей задачей в данный момент. Все алгоритмы разбора, которые бутут здесь описаны называются алгоритмами слева направо ввиду того, что они обрабатывают сначала самые левые символы обрабатываемой цепочки и продвигаются по цепочке только тогда, когда это необходимо.
Шпаргалки по Fortrany
Автоматические массивы В процедуре может быть задан локальный массив, размеры которого могут меняться при разных вызовах процедуры. Такие массивы, так же как и локальные строки переменной длины (разд. 10.4), относятся к автоматическим объектам.
Нахождение пути от одного населённого пункта к другому
Цель работы: Разработать программу, осуществляющую нахождение пути от одного населённого пункта к другому. Введение В настоящее время индустрия производства компьютеров и программного обеспечения для них является одной из наиболее важных сфер экономики развитых стран. Ежегодно в мире продаются десятки миллионов компьютеров.
Prolog. Реализация на ПЭВМ
Интегрированная среда языка Turbo Prolog. Структура программы на TURBO PROLOG. Предикаты работы с символьными данными. Работа с командами операционной системы.
Программирование на Турбо Паскале
Правила описания множественных типов данных, приемов использования множеств и операций над множествами в Паскаль-программах. Разработка в Турбо Паскале программы вывода всех согласных букв, которые входят хотя бы в одно слово заданного предложения.
Комбинаторные задачи
Решение задач по информатике, перебор различных комбинаторных конфигураций объектов и выбор наилучшего, с точки зрения условия задачи. Генерация k-элементных подмножеств, всех подмножеств данного множества, всех перестановок n-элементного множества.
Односвязный список на основе указателей
Рассмотрение понятия абстрактного типа данных. Реализация операций добавления элемента в пустой список и после указанных данных, удаления конкретного элемента и распечатки записей. Разработка интерфейса, исключающего нелигитимное модифицирование данных.
Рекурсия
С понятием рекурсии мы уже встречались: рекуррентные соотношения довольно часто встречаются в математических выражениях. Рекурсия в определении состоит в том, что определяемое понятие определяется через само это понятие.
Подпрограммы (процедуры и функции)
Алгоритм, ранее разработанный и целиком используемый в составе других алгоритмов, называется вспомогательным. Применение вспомогательных алгоритмов позволяет разбить задачу на части, структурировать ее.
Язык программирования Пролог 2
Лабораторная работа №1. Цель работы: Изучить основные конструкции языка программирования Пролог для решения задач вычисления функций в экспертных системах.
Построение математических моделей методом идентификации
Реферат Курсовая работа включает в себя 5 заданий. В первом задании по заданным экспериментальным данным необходимо построить линейную модель (множественную регрессию) методом наименьших квадратов, а также взвешенным методом наименьших квадратов для неравноточных измерений входной величины.
Нахождение пути от одного населённого пункта к другому
Цель работы: Разработать программу, осуществляющую нахождение пути от одного населённого пункта к другому. Введение В настоящее время индустрия производства компьютеров и программного обеспечения для них является одной из наиболее важных сфер экономики развитых стран. Ежегодно в мире продаются десятки миллионов компьютеров.
Коллективное использование произведений
Министерство общего и профессионального образования Российской федерации Южно–Уральский Государственный Университет Златоустовский Филиал Факультет Экономики и Права