Рекурсия. Уроки PHP. Рекурсия Php функция которая возвращает факториал числа
Данный урок посвящен рекурсии в PHP. Из функции можно вызывать другую функцию. Программа может вызвать функцию f1(), которая вызывает функцию f2(), и т.д. Вызывающая себя функция называется рекурсивной. Такой тип рекурсии называется явной рекурсией. Если функция f1() вызывает другую функцию f2(), которая в свою очередь вызывает функцию f1(), то эти функции также рекурсивные. Такой тип рекурсии называется неявной рекурсией. Очевидно, что возможны более сложные формы неявной рекурсии.
Предположим, что для решения некоторой задачи нужно создать рекурсивную функцию. В этом уроке опишем одну из известных стратегий решения задачи с использованием рекурсивной функции. Процесс рекурсивного решения задачи разделяется на этапы. На первом шаге для решения задачи вызывается рекурсивная функция. В этой функции задача решается для простейшей ситуации. Простейшая ситуация данной задачи называется базисной задачей. Если функция используется для решения базисной задачи, то она возвращает решение или результат.
Если функция вызывается для решения задачи более сложной, чем базисная задача, то функция разделяет задачу на две части:
- часть 1, которую функция может решить;
- часть 2, которую функция не может решить.
Для применения рекурсии часть 2 должна быть подобна начальной задаче, но относительно меньше или проще.
Так как образовавшаяся в части 2 задача подобна начальной задаче, поэтому функция вызывает новый собственный экземпляр с целью обработки новой задачи. Это действие называется рекурсивным вызовом или шагом рекурсии.
Так как на каждом шаге рекурсии (при каждом рекурсивном вызове) задача делится на две части, поэтому то количество этих шагов рекурсии может быть достаточно большое.
Для завершения рекурсии рекурсивная функция должна образовать последовательность упрощающихся (уменьшающихся) задач, которые приближаются к базисной задаче. Когда, на каком-то шаге рекурсии, функция обнаруживает базисную задачу, она возвращает решение (результат) базисной задачи в предыдущий вызов (предыдущий шаг рекурсии). В этом вызове, в свою очередь, полученный результат объединяется с частью, которую функция может решить. Образовавшееся таким путем решение возвращается на шаг выше, и т.д. Так генерируется последний результат, который возвращается в начальную точку вызова рекурсивной функции. То есть, чтобы был возможен возврат, каждый шаг функции нужно строить таким образом, чтобы он содержал в себе зарезервированное слово return.
Для демонстрации вышеизложенной идеи приведем пример использования рекурсивной функции.
Пример 1. Факториал. Факториал целого неотрицательного числа n равен n*(n-1)*(n-2)*...2*1 и обозначается n!. Принято, что 1!=1 и 0!=1. Например, 7!=7*6*5*4*3*2*1=5040.
Итеративное (нерекурсивное) решение для вычисления факториала таково (файл factorial1.php):
Вычисление факториала
";
exit;
}
$f=1;
for($i=$n;$i>=1;$i--)
$f*=$i;
echo "$n!=$f";
?>
Пусть f(n)=n!, тогда
f(n)=n!=n*(n-1)!=n*f(n-1),
то есть рекурсивная формула вычисления факториала такова:
f(n)=n*f(n-1).
Пример:
f(5)=5*f(4)=5*4*f(3)=5*4*3*f(2)= 5*4*3*2*f(1)= 5*4*3*2*1=120.
На основе рекурсивной формулы составим рекурсивную функцию для вычисления факториала (файл factorial2.php):
Вычисление факториала
if(!isset($_GET["n"]) || ($n = $_GET["n"])=="") {
echo "Введите натуральное число!
";
exit;
}
$f=factorial($n);
echo "$n!=$f";
function factorial($i) {
if($i<2) return 1;
$k=$i*factorial($i-1);
return $k;
}
?>
Если в программу ввести число 5, то для вычисления 5! программа действует следующим образом:
При первом вызове функции factorial() проверяется является ли посланное функции число меньше 2. Если полученное функцией число не меньше 2, то задача больше или сложнее базисной задачи, следовательно, задача делится на две части:
- $k=$i* - часть 1, которую функция может решить;
- factorial($n-1) – часть 2, которую функция не может решить.
Это действие повторяется до получения базисной задачи, то есть до вызова factorial(1). Если число меньше 2 (1 или 0), то функция factorial() возвращает число 1 ($k=1), то есть решается базисная задача. Если данный экземпляр функции factorial() был вызван ранее другим экземпляром функции factorial(), то результат возвращается вызвавшему экземпляру функции. Там возращенный результат $k умножается на переданный функции параметр $n и присваивается $k. Если данный экземпляр функции factorial() был вызван ранее другим экземпляром функции factorial(), то результат возвращается вызвавшему экземпляру функции и описанный процесс повторяется. Если данный экземпляр функции factorial() был вызван из главной части программы, то $k возвращается в эту часть, где результат выводится на экран и работа программы завершается.
Может ли кто-нибудь объяснить мне рекурсивную функцию в PHP (без использования Фибоначчи) на языке неспециалистов и на примерах? Я искал пример, но Фибоначчи полностью потерял меня!
Заранее спасибо;-) Кроме того, как часто вы используете их в веб-разработке?
17 ответов 17
Условия Laymens:
Рекурсивная функция - это функция, которая сама вызывает
Чуть подробнее:
Если функция продолжает вызывать себя, как она узнает, когда остановиться? Вы создали условие, известное как базовый вариант. Базовые случаи сообщают нашему рекурсивному вызову, когда нужно остановиться, иначе он будет повторяться бесконечно.
Хорошим примером обучения для меня, так как я хорошо разбираюсь в математике, был
<--calling itself. } }
Что касается использования рекурсивных функций в веб-разработке, я лично не прибегаю к использованию рекурсивных вызовов. Не то чтобы я считал плохой практикой полагаться на рекурсию, но они не должны быть вашим первым вариантом. Они могут быть смертельными, если не используются должным образом.
Хотя я не могу конкурировать с примером каталога, я надеюсь, что это поможет.
(20.04.10) Обновление:
Также было бы полезно проверить этот вопрос, где принятый ответ демонстрирует в терминах непрофессионалов, как работает рекурсивная функция. Несмотря на то, что вопрос ОП касался Java, концепция та же самая,
2017-05-23 11: 33: 24Z
Примером может быть печать каждого файла в любых подкаталогах данного каталога (если у вас нет символических ссылок внутри этих каталогов, которые могут как-то нарушать функцию). Псевдокод печати всех файлов выглядит следующим образом:
Function printAllFiles($dir) { foreach (getAllDirectories($dir) as $f) { printAllFiles($f); // here is the recursive call } foreach (getAllFiles($dir) as $f) { echo $f; } }
Идея состоит в том, чтобы сначала распечатать все подкаталоги, а затем файлы текущего каталога. Эта идея применяется ко всем подкаталогам, и это является причиной рекурсивного вызова этой функции для всех подкаталогов.
Если вы хотите попробовать этот пример, вы должны проверить специальные каталоги. и.. , в противном случае вы все время застреваете в вызове printAllFiles(".") . Кроме того, вы должны проверить, что печатать и каков ваш текущий рабочий каталог (см. opendir() , getcwd() , ...).
2013-11-18 14: 16: 52Z
Рекурсия - это то, что повторяется. Как функция, которая вызывает себя изнутри. Позвольте мне продемонстрировать несколько псевдо-пример:
Представь, что твои приятели пьют пиво, но твоя жена собирается тебя убить, если ты не вернешься домой до полуночи. Для этого давайте создадим функцию orderAndDrinkBeer ($time), где $time - полночь минус время, потраченное на завершение напитка и возвращение домой.
Итак, придя в бар, вы заказываете свое первое пиво и начинаете пить:
$timeToGoHome = "23"; // Let"s give ourselves an hour for last call and getting home function orderAndDrinkBeer($timeToGoHome) { // Let"s create the function that"s going to call itself. $beer = New Beer(); // Let"s grab ourselves a new beer $currentTime = date("G"); // Current hour in 24-hour format while ($beer->status != "empty") { // Time to commence the drinking loop $beer->drink(); // Take a sip or two of the beer(or chug if that"s your preference) } // Now we"re out of the drinking loop and ready for a new beer if ($currentTime < $timeToGoHome) { // BUT only if we got the time orderAndDrinkBeer($timeToGoHome); // So we make the function call itself again! } else { // Aw, snap! It is time:S break; // Let"s go home:(} }
Теперь давайте просто надеяться, что вы не смогли выпить достаточно пива, чтобы стать настолько опьяненными, что ваша жена заставит вас спать на диване, несмотря на то, что вы не дома вовремя -.-
Но да, именно так и происходит рекурсия.
2010-10-27 10: 59: 35Z
Это функция, которая вызывает сама себя. Это полезно для обхода определенных структур данных, которые повторяются, таких как деревья. 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) { //Increment our depth counter and check i++; if (i > depth) depth = i; //call this function again for each of the branch nodes (recursion!) if (node.left != null) walkTree(node.left, i); if (node.right != null) walkTree(node.right, i); //Decrement our depth counter before going back up the call stack i--; }
Наконец, мы вызываем функцию
Alert("Tree depth:" + walkTree(tree, 0));
Отличным способом понимания рекурсии является пошаговое выполнение кода во время выполнения.
2010-04-15 22: 15: 09Z
Это очень просто, когда функция вызывает себя для выполнения задачи для неопределенного и конечного числавремя Пример из моего собственного кода, функция для заполнения многоуровневым деревом категорий
Function category_tree($parent=0,$sep="") { $q="select id,name from categorye where parent_id=".$parent; $rs=mysql_query($q); while($rd=mysql_fetch_object($rs)) { echo("id."">".$sep.$rd->name.""); category_tree($rd->id,$sep."--"); } }
2010-10-27 12: 44: 20Z
Рекурсия - это причудливый способ сказать: «Делай это снова, пока не сделаешь».
Две важные вещи:
- Базовый случай. У вас есть цель, к которой можно добраться.
- Тест - как узнать, попал ли ты туда, куда собираешься.
Представьте себе простую задачу: сортируйте стопку книг по алфавиту. Простым процессом было бы взять первые две книги, отсортировать их. Теперь вот рекурсивная часть: есть ли еще книги? Если так, сделайте это снова. «Сделай это снова» - это рекурсия. «Есть ли еще книги» - это тест. И «нет, книг больше нет» - это базовый случай.
2010-04-15 21: 48: 00Z
Это потому, что одно:
Функция при вызове создается в памяти (создается новый экземпляр)
Таким образом, рекурсивная функция НЕ ВЫЗЫВАЕТСЯ , а вызывает другой экземпляр - так что в памяти нет ни одной функции, выполняющей магию. Его пара экземпляров в памяти, которые возвращают себе некоторые значения - и это поведение такое же, когда, например, функция a вызывает функцию b. У вас есть два экземпляра, а также если бы рекурсивная функция вызывала новый экземпляр самого себя.
Попробуйте нарисовать память экземплярами на бумаге - это будет иметь смысл.
2017-04-14 05: 17: 49Z
Рекурсия - это альтернатива циклам, они редко придают вашему коду большую ясность или элегантность. Хороший пример был дан ответом Progman: если он не будет использовать рекурсию, он будет вынужден отслеживать, в каком каталоге он в настоящее время (это называется состоянием) рекурсии, позволяет ему вести бухгалтерию, используя стек (область, где переменные и обратный адрес метода сохраняются)
Стандартные примеры факториала и Фибоначчи бесполезны для понимания концепции, поскольку их легко заменить циклом.
2010-04-15 21: 46: 11Z
В основном это. Он продолжает называть себя, пока не закончится
Void print_folder(string root) { Console.WriteLine(root); foreach(var folder in Directory.GetDirectories(root)) { print_folder(folder); } }
Также работает с циклами!
Void pretend_loop(int c) { if(c==0) return; print "hi"; pretend_loop(c-); }
Вы также можете попробовать поискать его в Google. Обратите внимание на «Вы имели в виду» (нажмите на него...). http://www.google.com/search?q=recursion&spell= 1 р>
2015-08-14 09: 56: 52Z
Вот практический пример (уже есть несколько хороших). Я просто хотел добавить тот, который будет полезен практически любому разработчику.
В какой-то момент разработчикам потребуется проанализировать объект, как в ответе API или какого-либо типа объекта или массива.
Эта функция изначально вызывается для анализа объекта, который может содержать только параметры, но что, если объект также содержит другие объекты или массивы? Это нужно будет решить, и по большей части основная функцияуже делает это, поэтому функция просто вызывает себя снова (после подтверждения того, что ключ или значение является объектом или массивом) и анализирует этот новый объект или массив. В конечном итоге возвращается строка, которая создает каждый параметр в строке отдельно для удобства чтения, но вы также можете легко записать значения в файл журнала или вставить в БД или что-то еще.
Я добавил параметр $prefix , чтобы использовать родительский элемент для описания конечной переменной, чтобы мы могли видеть, к чему относится значение. Он не включает в себя такие вещи, как нулевые значения, но это можно изменить из этого примера.
Если у вас есть объект:
$apiReturn = new stdClass(); $apiReturn->shippingInfo = new stdClass(); $apiReturn->shippingInfo->fName = "Bill"; $apiReturn->shippingInfo->lName = "Test"; $apiReturn->shippingInfo->address1 = "22 S. Deleware St."; $apiReturn->shippingInfo->city = "Chandler"; $apiReturn->shippingInfo->state = "AZ"; $apiReturn->shippingInfo->zip = 85225; $apiReturn->phone = "602-312-4455"; $apiReturn->transactionDetails = array("totalAmt" => "100.00", "currency" => "USD", "tax" => "5.00", "shipping" => "5.00"); $apiReturn->item = new stdClass(); $apiReturn->item->name = "T-shirt"; $apiReturn->item->color = "blue"; $apiReturn->item->itemQty = 1;
и используйте:
Var_dump($apiReturn);
он вернется:
object (stdClass) # 1 (4) {["shippingInfo"] = > object (stdClass) # 2 (6) {["fName"] = > string (4) "Bill" ["lName"] = > string (4) "Test" ["address1"] = > Строка (18) "22 S. Deleware St." [ "Город"] = > string (8) "Chandler" ["state"] = > string (2) "AZ" ["zip"] = > int (85225)} ["phone"] = > string (12) "602-312-4455" ["actionDetails "] = > array (4) {["totalAmt"] = > string (6) "100.00" ["currency"] = > string (3) "USD" ["tax"] = > string (4) "5.00" ["shipping"] = > string (4) "5.00"} ["item"] = > object (stdClass) # 3 (3) {["name"] = > string (7) "Футболка" ["color"] = > string (4) "blue" ["itemQty"] = > int (1)}}
и вот код для его разбора на строку с разрывом строки для каждого параметра:
Function parseObj($obj, $prefix = ""){
$stringRtrn = "";
foreach($obj as $key=>$value){
if($prefix){
switch ($key) {
case is_array($key):
foreach($key as $k=>$v){
$stringRtrn .= parseObj($key, $obj);
}
break;
case is_object($key):
$stringRtrn .= parseObj($key, $obj);
break;
default:
switch ($value) {
case is_array($value):
$stringRtrn .= parseObj($value, $key);
break;
case is_object($value):
$stringRtrn .= parseObj($value, $key);
break;
default:
$stringRtrn .= $prefix ."_". $key ." = ". $value ."
";
break;
}
break;
}
} else { // end if($prefix)
switch($key){
case is_array($key):
$stringRtrn .= parseObj($key, $obj);
break;
case is_object($key):
$stringRtrn .= parseObj($key, $obj);
break;
default:
switch ($value) {
case is_array($value):
$stringRtrn .= parseObj($value, $key);
break;
case is_object($value):
$stringRtrn .= parseObj($value, $key);
break;
default:
$stringRtrn .= $key ." = ". $value ."
";
break;
} // end inner switch
} // end outer switch
} // end else
} // end foreach($obj as $key=>$value)
return $stringRtrn;
} // END parseObj()
Это вернет объект следующим образом:
ShippingInfo_fName = Bill shippingInfo_lName = Test shippingInfo_address1 = 22 S. Deleware St. shippingInfo_city = Chandler shippingInfo_state = AZ shippingInfo_zip = 85225 phone = 602-312-4455 transactionDetails_totalAmt = 100.00 transactionDetails_currency = USD transactionDetails_tax = 5.00 transactionDetails_shipping = 5.00 item_name = T-shirt item_color = blue item_itemQty = 1
Я сделал операторы вложенного переключателя , чтобы избежать путаницы с if . . . ifelse . . . else , но это было почти так же долго. Если это поможет, просто попросите условные выражения if, и я могу вставить их для тех, кто в этом нуждается.
2017-01-15 20: 40: 28Z
Хорошим примером является прогулка по дереву каталогов. Вы можете сделать что-то подобное для обработки массива. Вот действительно простая рекурсивная функция, которая просто обрабатывает строку, простой массив строк или вложенный массив строк любой глубины, заменяя экземпляры "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 («привет»), он вернет «до свидания». Если вы отправите ему массив строк, хотя он будет вызывать себя один раз для каждого члена массива, тогда верните обработанный массив.
2014-07-04 22: 16: 16Z
Если вы добавите определенное значение (скажем, «1») к примеру Энтони Форлони, все будет ясно:
Function fact(1) { if (1 === 0) { // our base case return 1; } else { return 1 * fact(1-1); // <--calling itself. } }
оригинал:
Function fact($n) { if ($n === 0) { // our base case return 1; } else { return $n * fact($n-1); // <--calling itself. } }
2014-07-21 06: 49: 29Z
Это очень простой пример факториала с помощью рекурсии:
Факториалы - это очень простая математическая концепция. Они написаны как 5! а это значит 5 * 4 * 3 * 2 * 1. Итак 6! это 720 и 4! это 24.
Function factorial($number) { if ($number < 2) { return 1; } else { return ($number * factorial($number-1)); } }
надеюсь, что это полезно для вас. :)
2015-09-15 07: 49: 11Z
Рекурсия, используемая для константы Капрекара
Function KaprekarsConstant($num, $count = 1) { $input = str_split($num); sort($input); $ascendingInput = implode($input); $descendingInput = implode(array_reverse($input)); $result = $ascendingInput > $descendingInput ? $ascendingInput - $descendingInput: $descendingInput - $ascendingInput; if ($result != 6174) { return KaprekarsConstant(sprintf("%04d", $result), $count + 1); } return $count;
Функция продолжает вызывать себя с результатом вычисления, пока не достигнет константы Капрекарса, при которой она будет возвращать количество раз, когда были выполнены вычисления.
/edit Для тех, кто не знает константу Капрекара, требуется ввод 4 цифр, по крайней мере, с двумя разными цифрами.
2018-03-02 07: 34: 31Z
Я тоже не нахожу примеры полезными. Вы не можете решить две проблемы одновременно, когда математика вовлечена, ваш ум переключается между двумя проблемами. Хватит говорить
Пример: р>
У меня есть функция, в которой я взрываю строки в массив на основе разделителя: .
Public function explodeString($string) { return explode(":", $string); }
У меня есть другая функция, где я беру строки в качестве входных данных
Public function doRec() { $strings = [ "no:go", "hello:world", "nested" => [ "iam:good", "bad:array", "bad:how", "bad:about", ] ]; $response = ; foreach ($strings as $string) { array_push($response,$this->explodeString($string)); } return $response; }
Проблема в том, что у моего ввода есть вложенный массив, и моя функция explodeString получает тип string . Я могу переписать некоторый код в функции explodeString , чтобы приспособиться к этому, но мне все еще нужна та же функция для выполнения той же операции с моей строкой. Вот где я могу вызвать метод recursively в. Итак, вот последняя функция explodeString с рекурсией.
Public function explodeString($string) { if (is_array($string)) { $combine = ; foreach ($string as $str) { array_push($combine, $this->explodeString($str)); } return $combine; } return explode(":", $string); }
» Рекурсия
При объяснении решения задач математики очень часто применяют словосочетание «по индукции», которое многих ставит в тупик, так как это понятие является не самым простым. В программировании тоже имеется своеобразная индукция, называемая рекурсией .
Например, попробуем написать функцию с помощью обычного цикла for, возвращающую факториал числа. Из курса математики известно, что он вычисляется следующим образом: n! =1*2...*(n-1)*n. Причем 0!=1, а факториала отрицательных чисел не бывает (листинг 7.13).
Листинг 7.13. Функция нахождения факториала числа без рекурсии.
‹html›
‹head›
‹title›Функция нахождения факториала числа без рекурсии‹/title›
‹/head›
‹body›
‹?php
function factorial($num)
{
if ($num
{
return 0;
}
if ($num == 0)
{
return 1;
}
for ($i = 1, $sum = 1; $i
{
$sum = $sum * $i;
}
return $sum;
}
?›
‹/body›
‹/html›
Итак, задача решена, как говорится, «в лоб». В случае передачи отрицательных значений функция будет возвращать 0. Это реализуется с помощью первого оператора if. Далее если передано число 0, то возвращаем единицу. И наконец, в цикле for вычисляем факториал при любых других значениях.
При решении задач с помощью рекурсии требуются рассуждения иного рода. Например, факториал числа можно вычислить следующим образом:
n! = 1, если n=0
n! = n*(n-1)!, если n>0
Заметьте, что второе утверждение содержит в себе знак факториала. Именно в этом и состоит основной смысл рекурсии. При решении определенной задачи мы используем то, что нам нужно найти. В программировании функцию называют рекурсивной, если в ее описании присутствует обращение саму на себя.
Итак, вернемся к рассуждению о факториале. При решении задач с помощью рекурсии всегда надо иметь два типа утверждений: базисное и рекурсивное. В нашем случае базисным утверждением является n! = 1, если n = 0. Как вы, наверное, уже догадались, работая с рекурсивным утверждением, мы должны перейти к базисному и получить результат. Теперь попробуем реализовать все это на практике (листинг 7.14).
Листинг 7.14. Функция нахождения факториала числа с рекурсией
‹html›
‹head›
‹title›Функция нахождения факториала числа с рекурсией‹/title›
‹/head›
‹body›
‹?php
function factorial($num)
{
if ($num
{
return 0;
}
if ($num == 0)
{
return 1;
}
return $num*factorial($num-1); // рекурсивный вывод
}
echo factorial(3); // выведет 6
?›
‹/body›
‹/html›
В этом случае первые два условия аналогичны примеру, разобранному выше. Но теперь вместо цикла fоr мы записываем рекурсивное выражение, в котором функция вызывает сама себя. В нашей программе это происходит до тех пор, пока в качестве входного параметра не будет число 0, при котором функция возвратит 1. Причем это значение возвратится не в основную программу, а в тело предыдущей функции. Эта функция, в свою очередь, возвратит свое значение в тело следующей функции и т. д., пока нужное значение не возвратится в основную программу.
