Что с точки зрения непрофессионала - это рекурсивная функция, использующая PHP - PullRequest
71 голосов
/ 16 апреля 2010

Может ли кто-нибудь объяснить мне рекурсивную функцию в PHP (без использования Фибоначчи) на языке неспециалистов и на примерах? я смотрел на пример, но Фибоначчи полностью потерял меня!

Заранее спасибо ;-) Кроме того, как часто вы используете их в веб-разработке?

Ответы [ 17 ]

87 голосов
/ 16 апреля 2010

Сроки Laymens:

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

Чуть подробнее:

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

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

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

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

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

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

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

31 голосов
/ 16 апреля 2010

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

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

22 голосов
/ 27 октября 2010

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

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

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

Но да, именно так и происходит рекурсия.

9 голосов
/ 16 апреля 2010

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

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

7 голосов
/ 16 апреля 2010

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

5 голосов
/ 27 октября 2010

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

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.'--');
    }
}
4 голосов
/ 16 апреля 2010

Рекурсия - это причудливый способ сказать "Делай это снова, пока это не будет сделано".

Две важные вещи, которые нужно иметь:

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

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

2 голосов
/ 14 апреля 2017

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

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

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

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

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

1 голос
/ 20 июля 2015

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

В какой-то момент разработчикам потребуется проанализировать объект, как в ответе 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" ["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) "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

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

1 голос
/ 16 апреля 2010

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

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

...