O que em termos leigos é uma function recursiva usando PHP

Alguém pode por favor explicar uma function recursiva para mim em PHP (sem usar Fibonacci) em linguagem layman e usando exemplos? Eu estava olhando para um exemplo, mas o Fibonacci totalmente me perdeu!

Agradeço antecipadamente 😉 Também com que frequência você os utiliza no desenvolvimento web?

Termos de Laymens:

Uma function recursiva é uma function que se chama

Um pouco mais em profundidade:

Se a function continuar chamando a si mesma, como ela sabe quando parar? Você configura uma condição, conhecida como um caso base. Casos básicos informam nossa chamada recursiva quando parar, caso contrário, ela será ativada infinitamente.

O que foi um bom exemplo de aprendizado para mim, já que tenho uma sólida formação em matemática, era fatorial . Pelos comentários abaixo, parece que a function fatorial pode ser um pouco demais, vou deixar aqui apenas no caso de você querer.

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

No que diz respeito ao uso de funções recursivas no desenvolvimento web, eu pessoalmente não recorro ao uso de chamadas recursivas. Não que eu considerasse uma prática ruim contar com recursion, mas eles não deveriam ser sua primeira opção. Eles podem ser mortais se não forem usados ​​corretamente.

Embora eu não possa competir com o exemplo de diretório, espero que isso ajude um pouco.

(20/04/10) Atualização:

Também seria útil verificar essa questão, onde a resposta aceita demonstra em termos leigos como funciona uma function recursiva. Mesmo que a questão do OP tenha lidado com Java, o conceito é o mesmo,

  • Entendendo a recursion básica

Um exemplo seria imprimir todos os arquivos em quaisquer subdiretórios de um determinado diretório (se você não tiver nenhum link simbólico dentro desses diretórios, o que pode quebrar a function de alguma forma). Um pseudo-código de impressão de todos os arquivos é semelhante ao seguinte:

 function printAllFiles($dir) { foreach (getAllDirectories($dir) as $f) { printAllFiles($f); // here is the recursive call } foreach (getAllFiles($dir) as $f) { echo $f; } } 

A idéia é imprimir todos os subdiretórios primeiro e depois os arquivos do diretório atual. Essa ideia é aplicada a todos os subdiretórios, e essa é a razão para chamar essa function recursivamente para todos os subdiretórios.

Se você quiser tentar este exemplo, você deve verificar os diretórios especiais . e .. , caso contrário, você fica preso em chamar printAllFiles(".") o tempo todo. Além disso, você deve verificar o que imprimir e qual seu diretório de trabalho atual (consulte opendir() , getcwd() , …).

Recursão é algo que se repete. Como uma function que se chama de dentro de si. Deixe-me demonstrar em um exemplo um pouco pseudo:

Imagine que você está com seus amigos bebendo cerveja, mas sua esposa vai lhe dar um inferno se você não voltar para casa antes da meia-noite. Para este propósito, vamos criar a function orderAndDrinkBeer ($ time) onde $ time é meia-noite menos o tempo que você leva para terminar sua bebida atual e chegar em casa.

Então, chegando ao bar, você pede sua primeira cerveja e começa a beber:

 $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 :( } } 

Agora vamos apenas esperar que você não tenha bebido cerveja suficiente para ficar tão intoxicado que sua esposa vai fazer você dormir no sofá, independentemente de estar em casa na hora certa.-

Mas sim, é bem assim que a recursion acontece.

É uma function que se chama. É útil para andar certas estruturas de dados que se repetem, como trees. Um DOM HTML é um exemplo clássico.

Um exemplo de estrutura de tree em javascript e uma function recursiva para “andar” na tree.

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

Para percorrer a tree, chamamos a mesma function repetidamente, passando os nós filhos do nó atual para a mesma function. Em seguida, chamamos a function novamente, primeiro no nó esquerdo e depois à direita.

Neste exemplo, vamos obter a profundidade máxima da tree

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

Finalmente nós chamamos a function

 alert('Tree depth:' + walkTree(tree, 0)); 

Uma ótima maneira de entender a recursion é percorrer o código em tempo de execução.

Simplificando: Uma function recursiva é uma function que chama a si mesma.

Recursão é uma maneira chique de dizer “Faça isso de novo até que seja feito”.

Duas coisas importantes para ter:

  1. Um caso base – Você tem uma meta para chegar.
  2. Um teste – como saber se você tem onde você está indo.

Imagine uma tarefa simples: classifique uma pilha de livros em ordem alfabética. Um processo simples seria pegar os dois primeiros livros, classificá-los. Agora vem a parte recursiva: há mais livros? Se sim, faça de novo. O “faça de novo” é a recursion. O “há mais livros” é o teste. E “não, não há mais livros” é o caso base.

É muito simples, quando uma function chama a si mesma para realizar uma tarefa por tempo indefinido e finito. Um exemplo do meu próprio código, function para preencher uma tree de categorias com vários níveis

  function category_tree ($ parent = 0, $ sep = '')
 {
     $ q = "selecione id, nome da categoriae onde parent_id =". $ parent;
     $ rs = mysql_query ($ q);
     while ($ rd = mysql_fetch_object ($ rs))
     {
         echo ('id.' "'. $ sep. $ rd-> nome.' ');
         category_tree ($ rd-> id, $ sep. '-');
     }
 } 

A melhor explicação que encontrei quando descobri que estou aqui: http://www.elated.com/articles/php-recursive-functions/

É porque uma coisa:

A function quando seu chamado é criado na memory (nova instância é criada)

Assim, a function recursiva NÃO ESTÁ CALANDO-SE , mas chamando-a de outra instância – portanto, não é uma function na memory que faz alguma mágica. Seu par de instâncias na memory que estão retornando alguns valores – e esse comportamento é o mesmo quando, por exemplo, a function está chamando b. Você tem duas instâncias, bem como se a function recursiva chamada nova instância de si mesmo.

Tente desenhar memory com instâncias no papel – isso fará sentido.

A recursion é uma alternativa aos loops, é muito raro que eles tragam mais clareza ou elegância ao seu código. Um bom exemplo foi dado pela resposta de Progman, se ele não usasse a recursion, ele seria forçado a rastrear em qual diretório ele está atualmente (isso é chamado de estado) recursões lhe permitem fazer a contabilidade usando a pilha (a área onde variables e endereço de retorno de um método são armazenados)

Os exemplos padrão factorial e Fibonacci não são úteis para entender o conceito porque são fáceis de replace por um loop.

Basicamente isso. Ele continua chamando a si mesmo até que seja feito

 void print_folder(string root) { Console.WriteLine(root); foreach(var folder in Directory.GetDirectories(root)) { print_folder(folder); } } 

Também funciona com loops!

 void pretend_loop(int c) { if(c==0) return; print "hi"; pretend_loop(c-); } 

Você também pode tentar pesquisá-lo. Observe o “Você quis dizer” (clique sobre ele …). http://www.google.com/search?q=recursion&spell=1

Aqui está um exemplo prático (já existem vários bons). Eu só queria adicionar um que é útil para quase qualquer desenvolvedor.

Em algum momento, os desenvolvedores precisarão analisar um object como uma resposta de uma API ou algum tipo de object ou matriz.

Esta function é inicialmente chamada para analisar um object que pode conter apenas parâmetros, mas e se o object também contiver outros objects ou matrizes? Isso precisará ser tratado e, na maioria das vezes, a function básica já faz isso, portanto a function apenas chama a si mesma novamente (após confirmar que a chave ou valor é um object ou uma matriz) e analisa esse novo object ou matriz. Em última análise, o que é retornado é uma cadeia que cria cada parâmetro em uma linha por si só para facilitar a leitura, mas você pode facilmente registrar os valores em um arquivo de log ou inserir em um database ou qualquer outra coisa.

Eu adicionei o parâmetro $prefix para usar o elemento pai para ajudar a descrever a variável final para que possamos ver a que o valor pertence. Não inclui itens como valores nulos, mas isso pode ser alterado a partir deste exemplo.

Se você tiver o object:

 $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; 

E use:

 var_dump($apiReturn); 

ele retornará:

object (stdClass) # 1 (4) {[“shippingInfo”] => object (stdClass) # 2 (6) {[“fName”] => string (4) “Bill” [“lName”] => string ( 4) “Test” [“address1”] => string (18) “22 S. Deleware St.” [“cidade”] => string (8) “Chandler” [“estado”] => string (2) “AZ” [“zip”] => int (85225)} [“telefone”] => string (12 ) “602-312-4455” [“transactionDetails”] => array (4) {[“totalAmt”] => string (6) “100.00” [“moeda”] => string (3) “USD” [” tax “] => string (4)” 5.00 “[” shipping “] => string (4)” 5.00 “} [” item “] => object (stdClass) # 3 (3) {[” nome “] = > string (7) “T-shirt” [“cor”] => string (4) “azul” [“itemQty”] => int (1)}}

e aqui está o código para analisá-lo em uma string com uma quebra de linha para cada parâmetro:

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

Isso retornará o object da seguinte maneira:

 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 

Eu fiz as declarações de switch aninhadas para evitar confusão com if . . . ifelse . . . else if . . . ifelse . . . else if . . . ifelse . . . else , mas foi quase tanto tempo. Se isso ajudar, basta solicitar as condicionais if e posso colá-las para quem precisar.

Percorrer uma tree de diretórios é um bom exemplo. Você pode fazer algo semelhante para processar um array. Aqui está uma function recursiva realmente simples que simplesmente processa uma string, um array simples de strings, ou um array nested de strings de qualquer profundidade, substituindo instâncias de ‘hello’ por ‘goodbye’ na string ou os valores da array ou qualquer 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 } 

Sabe quando sair porque em algum momento, a “coisa” que está processando não é uma matriz. Por exemplo, se você chamar replaceHello (‘olá’), ele retornará ‘adeus’. Se você enviar uma matriz de strings, ela será chamada uma vez para cada membro da matriz e retornará a matriz processada.

Se você adicionar um determinado valor (digamos, “1”) ao exemplo de Anthony Forloney, tudo ficará claro:

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

original:

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

Este é um exemplo muito simples de fatorial com Recursão:

Factorials são um conceito matemático muito fácil. Eles estão escritos como 5! e isso significa 5 * 4 * 3 * 2 * 1. Então 6! é 720 e 4! é 24.

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

Espero que isso seja útil para você. 🙂

Funciona um exemplo simples recursivo (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); ?> 

Recursão usada para a constante de Kaprekar

 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; 

}

A function continua chamando-se com o resultado do cálculo até atingir a constante Kaprekars, na qual retornará a quantidade de vezes que os cálculos foram feitos.

/ edit Para quem não conhece o Kaprekars Constant, ele precisa de uma input de 4 dígitos com pelo menos dois dígitos distintos.