Что такое функция RECURSIVE в PHP?

Условия Laymens:

Рекурсивная функция – это функция, которая называет себя

Немного более подробно:

Если функция продолжает называть себя, как она знает, когда остановиться? Вы создали условие, известное как базовый случай. Базовые случаи говорят о нашем рекурсивном вызове, когда останавливаться, иначе он будет циклически бесконечно.

Для меня это был хороший пример обучения, поскольку у меня был сильный опыт в математике, был факториалом . По комментариям ниже, кажется, что факториальная функция может быть слишком большой, я оставлю ее здесь на всякий случай, если вы этого захотите.

function fact($n) { if ($n === 0) { // our base case return 1; } else { return $n * fact($n-1); // <--calling itself. } } 

Что касается использования рекурсивных функций в веб-разработке, я лично не прибегаю к использованию рекурсивных вызовов. Не то чтобы я считал, что плохая практика полагается на рекурсию, но они не должны быть вашим первым вариантом. Они могут быть смертельными, если их не использовать должным образом.

Хотя я не могу конкурировать с примером каталогов, я надеюсь, что это поможет.

(4/20/10) Обновление:

Было бы также полезно проверить этот вопрос, когда принятый ответ демонстрирует в мирянах, как работает рекурсивная функция. Несмотря на то, что вопрос OP касался Java, концепция такая же,

• Понимание базовой рекурсии

Примером может быть печать каждого файла в любых подкаталогах данного каталога (если у вас нет символических ссылок внутри этих каталогов, которые могут каким-то образом нарушить функцию). Псевдокод для печати всех файлов выглядит следующим образом:

 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() , …).

Рекурсия – это нечто повторяющееся. Как функция, которая называет себя внутри себя. Позвольте мне продемонстрировать несколько псевдо-пример:

Представьте, что вы с приятелями пьете пиво, но ваша жена собирается дать вам ад, если вы не придете домой до полуночи. Для этого давайте создадим функцию 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 :( } } 

Теперь давайте просто надеемся, что вы не сможете выпить достаточно пива, чтобы стать настолько опьяненным, что ваша жена собирается заставить вас спать на диване, независимо от того, чтобы быть дома вовремя.

Но да, это в значительной степени рекурсия.

Его функция, которая называет себя. Это полезно для перехода к определенным структурам данных, которые повторяются, например деревья. 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)); 

Отличным способом понимания рекурсии является переход кода во время выполнения.

Проще говоря: Рекурсивная функция – это функция, которая вызывает себя.

Рекурсия – это причудливый способ сказать «Повторить эту вещь до тех пор, пока она не закончится».

Две важные вещи:

1. Базовый корпус. У вас есть цель.
2. Тест. Как узнать, есть ли у вас, куда вы направляетесь.

Представьте себе простую задачу: сортируйте стопку книг по алфавиту. Простой процесс будет занимать первые две книги, сортировать их. Теперь вот рекурсивная часть: есть ли еще книги? Если да, сделайте это снова. «Повторить это снова» – это рекурсия. «Есть ли больше книг» – это тест. И «нет, больше нет книг» является базовым случаем.

Это очень просто, когда функция вызывает себя для выполнения задачи для неопределенного и конечного количества времени. Пример из моего собственного кода, функция для заполнения многоуровневого дерева категорий

  function category_tree ($ parent = 0, $ sep = '')
 {
     $ q = "select id, name from categorye, где parent_id =". $ parent;
     $ Rs = mysql_query ($ д);
     в то время как ($ е = mysql_fetch_object ($ RS))
     {
         эхо ( 'идентификатор'. "> '» $ Сентября $ RD-> имя...');
         category_tree ($ RD-> ID, $ Сентябре .'-- ');
     }
 } 

Рекурсия является альтернативой циклам, редко бывает, что они привносят больше четкости или элегантности в ваш код. Хороший пример был дан ответом Прогмана, если он не будет использовать рекурсию, он будет вынужден отслеживать, в каком каталоге он в настоящее время (это называется state) рекурсии позволяют ему делать бухгалтерию с использованием стека (область, где переменные и возвращаемый адрес метода сохраняются)

Стандартные примеры factorial и Fibonacci не полезны для понимания концепции, потому что их легко заменить на цикл.

В основном это. Он продолжает называть себя до его завершения

 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-); } 

Вы также можете попробовать его. Обратите внимание на «Вы имели в виду» (щелкните по нему …). http://www.google.com/search?q=recursion&spell=1

Вот практический пример (уже есть несколько хороших). Я просто хотел добавить тот, который полезен почти любому разработчику.

В какой-то момент разработчикам необходимо будет проанализировать объект как ответ от 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) «Тест» ["address1"] => string (18) "22 S. Deleware St." ["city"] => string (8) "Chandler" ["state"] => string (2) "AZ" ["zip"] => int (85225)} ["phone"] => string (12 ) "602-312-4455" ["transactionDetails"] => 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) "T-shirt" ["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 ."<br>"; 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 ."<br>"; 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 

Я сделал вложенные операторы switch, чтобы избежать путаницы с if . . . ifelse . . . else if . . . ifelse . . . else if . . . ifelse . . . else , но это было почти так же долго. Если это помогает, просто попросите условные условия if, и я могу вставить их для тех, кто в ней нуждается.

Хорошим примером является прогулка по дереву каталогов. Вы можете сделать что-то подобное процессу массива. Вот очень простая рекурсивная функция, которая просто обрабатывает строку, простой массив строк или вложенный массив строк любой глубины, заменяя экземпляры «привет» на «прощание» в строке или значениях массива или любой суб-массив:

 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'), он вернется «до свидания». Если вы отправите ему массив строк, хотя он будет называть себя один раз для каждого члена массива, тогда верните обработанный массив.

Если вы добавите определенное значение (например, «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. } } 

Это очень простой пример факториала с рекурсией:

Факториалы – очень простая математическая концепция. Они написаны как 5! и это означает 5 * 4 * 3 * 2 * 1. Итак, 6! 720 и 4! составляет 24.

 function factorial($number) { if ($number < 2) { return 1; } else { return ($number * factorial($number-1)); } } 

надеюсь, что это полезно для вас. 🙂

Он работает на простом примере рекурсивного (Y)

 <?php function factorial($y,$x) { if ($y < $x) { echo $y; } else { echo $x; factorial($y,$x+1); } } $y=10; $x=0; factorial($y,$x); ?> 

Лучшее объяснение, которое я нашел, когда узнал, что я здесь: http://www.elated.com/articles/php-recursive-functions/

Это потому, что одно:

Функция, когда ее вызываемый создается в памяти (создается новый экземпляр)

Таким образом, рекурсивная функция НЕ ВЫЗВАЛА СЕБЯ , но вызывает ее другой экземпляр – поэтому его не одна функция в памяти делает какую-то магию. Его несколько экземпляров в памяти, которые возвращают себе некоторые значения – и это поведение одно и то же, когда, например, функция a вызывает функцию b. У вас есть два экземпляра, а также рекурсивная функция, называемая новым экземпляром.

Попробуйте нарисовать память с экземплярами на бумаге – это будет иметь смысл.