Может ли кто-нибудь объяснить мне рекурсивную функцию в PHP (без использования Фибоначчи) на обычном языке и на примерах?
Заранее спасибо ;-) Также: как часто вы используете их в веб-разработке?
Ответ 1
Термины Laymens:
Рекурсивная функция – это функция, которая вызывает сама себя.
Немного подробнее:
Если функция вызывает сама себя, как она узнает, когда необходимо остановиться? Вы задаете условие, известное как базовый случай. Базовые случаи говорят нашему рекурсивному вызову, когда остановиться, иначе он будет вызываться бесконечно.
Хорошим учебным примером для меня, поскольку я хорошо знаю математику, был факториал. Я оставлю этот пример здесь на всякий случай, если он вам нужен.
function fact($n) {
if ($n === 0) { // базовый случай
return 1;
} else {
return $n * fact($n-1); // <--вызов самой себя.
}
}
Что касается использования рекурсивных функций в веб-разработке, то лично я не прибегаю к использованию рекурсивных вызовов. Не то чтобы я считал использование рекурсии плохой практикой, но она не должна быть вашим первым вариантом. При неправильном использовании они могут быть непредсказуемы.
Ответ 2
Примером может быть печать каждого файла в любых подкаталогах данного каталога (если у вас нет символических ссылок внутри этих каталогов, которые могут каким-то образом нарушить работу функции). Псевдокод печати всех файлов выглядит так:
function printAllFiles($dir) {
foreach (getAllDirectories($dir) as $f) {
printAllFiles($f); // здесь рекурсивный вызов
}
foreach (getAllFiles($dir) as $f) {
echo $f;
}
}
Идея заключается в том, чтобы сначала вывести все подкаталоги, а затем файлы текущего каталога. Эта идея будет применена ко всем подкаталогам, и это причина рекурсивного вызова этой функции для всех подкаталогов.
Если вы хотите попробовать этот пример, вы должны проверить наличие специальных каталогов. Иначе вы застрянете в постоянном вызове printAllFiles("."). Кроме того, вы должны проверить, что печатать и каков ваш текущий рабочий каталог (см. opendir(), getcwd(), ...).
Ответ 3
Это функция, которая вызывает сама себя. Это полезно для прохождения определенных повторяющихся структур данных, таких как деревья. HTML DOM – классический пример.
Пример древовидной структуры в javascript и рекурсивной функции для «обхода» дерева.
1
/ \
2 3
/ \
4 5
-
var tree = {
id: 1,
left: {
id: 2,
left: null,
right: null
},
right: {
id: 3,
left: {
id: 4,
left: null,
right: null
},
right: {
id: 5,
left: null,
right: null
}
}
};
Чтобы пройти по дереву, мы повторно вызываем одну и ту же функцию, передавая дочерние узлы текущего узла той же функции. Затем мы снова вызываем функцию, сначала в левом узле, а затем в правом.
В этом примере мы получим максимальную глубину дерева:
var depth = 0;
function walkTree(node, i) {
//Увеличиваем счетчик глубины и проверяем
i++;
if (i > depth) depth = i;
//вызов этой функции снова для каждого из узлов ветви (рекурсия!)
if (node.left != null) walkTree(node.left, i);
if (node.right != null) walkTree(node.right, i);
//Уменьшаем наш счетчик глубины перед возвратом в стек вызовов
i--;
}
Наконец, мы вызываем функцию:
alert('Tree depth:' + walkTree(tree, 0));
Отличный способ понять рекурсию – выполнить трассировку кода во время выполнения.
Ответ 4
Это очень просто, когда функция вызывает себя для выполнения задачи в течение неопределенного и конечного количества времени. Пример из моего собственного кода – функция для заполнения многоуровневого дерева категорий:
function category_tree ($parent = 0, $sep = '') {
$q = "выберите идентификатор, имя из категории, где parent_id =".$parent;
$rs = mysql_query($q);
while($ rd = mysql_fetch_object ($rs)) {
echo ('id.' "> '.$sep. $rd-> name.' ');
category_tree ($rd-> id, $sep.'-- ');
}
}
Ответ 5
Хорошим примером является прохождение по дереву каталогов. Вы можете сделать что-то подобное для обработки массива. Вот действительно простая рекурсивная функция, которая просто обрабатывает строку, простой массив строк или вложенный массив строк любой глубины, заменяя экземпляры "hello" на "goodbye" в строке или значениях массива или любого подмассива:
function replaceHello($a) {
if (! is_array($a)) {
$a = str_replace('hello', 'goodbye', $a);
} else {
foreach($a as $key => $value) {
$a[$key] = replaceHello($value);
}
}
return $a
}
Она знает, когда выйти, потому что в какой-то момент «элемент», который она обрабатывает, не является массивом. Например, если вы вызовете replaceHello('hello'), она вернет 'goodbye'. Если вы отправите ей массив строк, она вызовет себя один раз для каждого члена массива, а затем вернет обработанный массив.
Web
