Может кто-нибудь объяснить рекурсивную функцию для меня на PHP (без использования Фибоначчи) на языке неспециалиста и с использованием примеров? я смотрел на пример, но Фибоначчи полностью потерял меня!
Спасибо заранее;-) Также как часто вы используете их в веб-разработке?
Рекурсивная функция - это функция, которая называет себя
Если функция продолжает называть себя, как она знает, когда остановиться? Вы создали условие, известное как базовый случай. Базовые случаи говорят о нашем рекурсивном вызове, когда останавливаться, в противном случае он будет бесконечно зацикливаться.
Что было хорошим примером для меня, так как у меня сильный опыт в математике, factorial. По комментариям ниже, кажется, что факториальная функция может быть слишком большой, я оставлю ее здесь на всякий случай, если вы этого захотите.
function fact($n) {
if ($n === 0) { // our base case
return 1;
}
else {
return $n * fact($n-1); // <--calling itself.
}
}
Что касается использования рекурсивных функций в веб-разработке, я лично не прибегаю к использованию рекурсивных вызовов. Не то чтобы я считал, что плохая практика полагается на рекурсию, но они не должны быть вашим первым вариантом. Они могут быть смертельными, если их не использовать должным образом.
Хотя я не могу конкурировать с примером каталогов, я надеюсь, что это немного поможет.
Было бы также полезно проверить этот вопрос, когда принятый ответ демонстрирует в мирянах, как работает рекурсивная функция. Несмотря на то, что вопрос ОП касался 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 give ourselves an hour for last call and getting home
function orderAndDrinkBeer($timeToGoHome) { // Let create the function that going to call itself.
$beer = New Beer(); // Let 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 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 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
}
}
};
Чтобы ходить по дереву, мы вызываем одну и ту же функцию повторно, передавая дочерние узлы текущего node той же функции. Затем мы вызываем функцию снова, сначала слева node, а затем справа.
В этом примере мы получим максимальную глубину дерева
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));
Отличным способом понимания рекурсии является переход кода во время выполнения.
Проще говоря: Рекурсивная функция - это функция, которая вызывает себя.
Это очень просто, когда функция вызывает себя для выполнения задачи для undefined и конечного количества времени. Пример из моего собственного кода, функция для заполнения дерева с многоуровневой категорией
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.'--');
}
} Рекурсия - это причудливый способ сказать "Делать эту вещь снова до ее завершения".
Две важные вещи:
Представьте себе простую задачу: сортируйте стопку книг по алфавиту. Простой процесс будет занимать первые две книги, сортировать их. Теперь вот рекурсивная часть: есть ли еще книги? Если да, сделайте это снова. "Повторить это снова" - это рекурсия. "Есть ли больше книг" - это тест. И "нет, больше нет книг" является базовым случаем.
Лучшее объяснение, которое я нашел, когда узнал, что я здесь: http://www.elated.com/articles/php-recursive-functions/
Это потому, что одна вещь:
Функция, когда ее вызываемый создается в памяти (создается новый экземпляр)
Итак, рекурсивная функция НЕ ВЫЗВАЛА СЕБЯ, но вызывает ее другой экземпляр - поэтому его не одна функция в памяти делает какую-то магию. Его несколько экземпляров в памяти, которые возвращают себе некоторые значения - и это поведение одно и то же, когда, например, функция a вызывает функцию b. У вас есть два экземпляра, а также рекурсивная функция, называемая новым экземпляром.
Попробуйте нарисовать память с экземплярами на бумаге - это будет иметь смысл.
В основном это. Он продолжает называть себя до его завершения.
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
Рекурсия - это альтернатива циклам, довольно редко, что они привносят в ваш код больше ясности или элегантности. Хороший пример был дан ответ Прогманом, если он не будет использовать рекурсию, он будет вынужден отслеживать, в каком каталоге он в настоящее время (это называется state) рекурсии позволяют ему вести бухгалтерский учет с использованием стека (область, где переменные и возвращаемый адрес метода сохраняются)
Стандартные примеры factorial и Fibonacci не полезны для понимания концепции, потому что они легко заменяются циклом.
Вот практический пример (уже есть несколько хороших). Я просто хотел добавить тот, который полезен почти любому разработчику.
В какой-то момент разработчикам необходимо будет проанализировать объект как ответ от 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" ] = > 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, и я могу вставить их для тех, кто в ней нуждается.
Прогулка по дереву каталогов - хороший пример. Вы можете сделать что-то подобное процессу массива. Вот очень простая рекурсивная функция, которая просто обрабатывает строку, простой массив строк или вложенный массив строк любой глубины, заменяя экземпляры "привет" на "прощание" в строке или значениях массива или любой sub-array:
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); ?>
Рекурсия для константы Капрекара
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 цифр, по крайней мере, с двумя разными цифрами.
Я тоже не нахожу примеры полезными. Вы не можете решить две проблемы одновременно, когда математика вовлечена, ваш ум переключается между двумя проблемами. Хватит болтать
Пример:
У меня есть функция, где я взрыва строк в массив на основе : разделитель.
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);
}