php - recursividad - funciones recursivas jquery
¿Qué es una función RECURSIVA en PHP? (16)
Términos de Laymens:
Una función recursiva es una función que se llama a sí misma
Un poco más en profundidad:
Si la función sigue llamándose a sí misma, ¿cómo sabe cuándo detenerse? Configura una condición, conocida como caso base. Los casos base le dicen a nuestra llamada recursiva cuándo detenerse, de lo contrario, se repetirá infinitamente.
Lo que fue un buen ejemplo de aprendizaje para mí, ya que tengo una sólida formación en matemáticas, fue factorial . En los comentarios a continuación, parece que la función factorial puede ser demasiado, la dejaré aquí por si acaso la quisieras.
function fact($n) {
if ($n === 0) { // our base case
return 1;
}
else {
return $n * fact($n-1); // <--calling itself.
}
}
Con respecto al uso de funciones recursivas en el desarrollo web, personalmente no recurro al uso de llamadas recursivas. No es que considere una mala práctica depender de la recursión, pero no deberían ser su primera opción. Pueden ser mortales si no se usan adecuadamente.
Aunque no puedo competir con el ejemplo del directorio, espero que esto ayude un poco.
(20/4/10) Actualización:
También sería útil verificar esta pregunta, donde la respuesta aceptada demuestra en términos sencillos cómo funciona una función recursiva. A pesar de que la pregunta de OP se refería a Java, el concepto es el mismo,
¿Alguien puede explicarme una función recursiva en PHP (sin usar Fibonacci) en lenguaje sencillo y con ejemplos? ¡Estaba viendo un ejemplo, pero los Fibonacci me perdieron por completo!
Gracias de antemano ;-) Además, ¿con qué frecuencia los usas en el desarrollo web?
Aquí hay un ejemplo práctico (ya hay varios buenos). Solo quería agregar uno que sea útil para casi cualquier desarrollador.
En algún momento, los desarrolladores necesitarán analizar un objeto como si fuera una respuesta de una API o algún tipo de objeto o matriz.
Esta función se llama inicialmente para analizar un objeto que puede contener parámetros, pero ¿y si el objeto también contiene otros objetos o matrices? Esto tendrá que ser abordado, y en su mayor parte la función básica ya lo hace, por lo que la función simplemente se llama de nuevo (después de confirmar que la clave o valor es un objeto o una matriz) y analiza este nuevo objeto o matriz. En última instancia, lo que se devuelve es una cadena que crea cada parámetro en una línea por sí misma para facilitar su lectura, pero también puede registrar los valores en un archivo de registro o insertarlos en un DB o lo que sea.
$prefix parámetro $prefix para usar el elemento padre para ayudar a describir la variable final para que podamos ver a qué se refiere el valor. No incluye cosas como valores nulos, pero esto se puede modificar a partir de este ejemplo.
Si tienes el objeto:
$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;
y use:
var_dump($apiReturn);
volverá:
object (stdClass) # 1 (4) {["shippingInfo"] => object (stdClass) # 2 (6) {["fName"] => cadena (4) "Bill" ["lName"] => string ( 4) "Test" ["address1"] => cadena (18) "22 S. Deleware St." ["ciudad"] => cadena (8) "Chandler" ["estado"] => cadena (2) "AZ" ["zip"] => int (85225)} ["phone"] => cadena (12 ) "602-312-4455" ["transactionDetails"] => array (4) {["totalAmt"] => cadena (6) "100.00" ["currency"] => string (3) "USD" [" tax "] => string (4)" 5.00 "[" shipping "] => cadena (4)" 5.00 "} [" item "] => object (stdClass) # 3 (3) {[" name "] = > string (7) "T-shirt" ["color"] => cadena (4) "azul" ["itemQty"] => int (1)}}
y aquí está el código para analizarlo en una cadena con un salto de línea 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 ."<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()
Esto devolverá el objeto de la siguiente manera:
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
Hice las declaraciones de cambio anidadas para evitar confusiones con if . . . ifelse . . . else if . . . ifelse . . . else if . . . ifelse . . . else , pero fue casi tan largo. Si esto ayuda, solo pregunta por los condicionales si y los puedo pegar para aquellos que lo necesiten.
Básicamente esto. Sigue llamándose hasta que esté hecho
void print_folder(string root)
{
Console.WriteLine(root);
foreach(var folder in Directory.GetDirectories(root))
{
print_folder(folder);
}
}
¡También funciona con bucles!
void pretend_loop(int c)
{
if(c==0) return;
print "hi";
pretend_loop(c-);
}
También puedes intentar buscar en Google. Tenga en cuenta el "¿Quiso decir?" (Haga clic en él ...). http://www.google.com/search?q=recursion&spell=1
En pocas palabras: una función recursiva es una función que se llama a sí misma.
Es muy simple, cuando una función se llama a sí misma para realizar una tarea por tiempo indefinido y finito. Un ejemplo de mi propio código, función para poblar un árbol de categorías multinivel
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.''--''); } }
Es una función que se llama a sí misma. Es útil para caminar ciertas estructuras de datos que se repiten, como los árboles. Un HTML DOM es un ejemplo clásico.
Un ejemplo de una estructura de árbol en javascript y una función recursiva para ''caminar'' por el árbol.
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 recorrer el árbol, llamamos a la misma función repetidamente, pasando los nodos secundarios del nodo actual a la misma función. Luego llamamos a la función nuevamente, primero en el nodo izquierdo y luego a la derecha.
En este ejemplo, obtendremos la profundidad máxima del árbol
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 llamamos a la función
alert(''Tree depth:'' + walkTree(tree, 0));
Una buena forma de entender la recursión es recorrer el código en tiempo de ejecución.
Este es un ejemplo muy simple de factorial con Recursión:
Los factoriales son un concepto matemático muy fácil. ¡Están escritos como 5! y esto significa 5 * 4 * 3 * 2 * 1. ¡Entonces 6! es 720 y 4! es 24.
function factorial($number) {
if ($number < 2) {
return 1;
} else {
return ($number * factorial($number-1));
}
}
Espero que esto sea útil para ti. :)
Funciona un ejemplo simple 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); ?>
La mejor explicación que encontré cuando estaba aprendiendo que yo mismo estaba aquí: http://www.elated.com/articles/php-recursive-functions/
Es porque una cosa:
La función cuando se llama se crea en la memoria (se crea una nueva instancia)
Entonces la función recursiva NO ES LLAMARSE a sí misma , sino que llama a otra instancia, por lo que no es una función en la memoria hacer algo de magia. Su par de instancias en la memoria están devolviendo algunos valores, y este comportamiento es el mismo cuando, por ejemplo, la función a llama a la función b. Tiene dos instancias y una función recursiva llamada nueva instancia de sí mismo.
Pruebe dibujar memoria con instancias en papel: tendrá sentido.
La recursión es algo que se repite. Como una función que se autodenomina desde sí misma. Permítanme demostrar en un pseudo ejemplo:
Imagina que estás fuera con tus amigos bebiendo cerveza, pero tu esposa te dará un infierno si no vuelves a casa antes de la medianoche. Para este propósito, creemos la función orderAndDrinkBeer ($ time) donde $ time es la medianoche menos el tiempo que le lleva terminar su bebida actual y llegar a casa.
Entonces, al llegar al bar, pides tu primera cerveza y comienzas 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 :(
}
}
Ahora esperemos que no hayas sido capaz de beber suficiente cerveza como para estar tan ebrio que tu esposa te hará dormir en el sofá a pesar de estar en casa a tiempo -.-
Pero sí, así es como funciona la recursividad.
La recursividad es una alternativa a los bucles, es muy raro que aporten más claridad o elegancia a su código. Un buen ejemplo fue dado por la respuesta de Progman, si no usara la recursividad se vería forzado a realizar un seguimiento en qué directorio está actualmente (esto se llama estado) recurrencias le permite hacer la contabilidad usando la pila (el área donde las variables y la dirección de retorno de un método se almacena)
Los ejemplos estándar factorial y Fibonacci no son útiles para entender el concepto porque son fáciles de reemplazar por un bucle.
La recursividad es una forma elegante de decir "Haz esto otra vez hasta que se haga".
Dos cosas importantes que tener:
- Un caso base: tienes un objetivo al que llegar.
- Una prueba: cómo saber si has llegado adonde vas.
Imagina una tarea simple: ordena alfabéticamente una pila de libros. Un proceso simple sería tomar los primeros dos libros, ordenarlos. Ahora, aquí viene la parte recursiva: ¿Hay más libros? Si es así, hazlo de nuevo. El "hacerlo de nuevo" es la recursión. El "¿hay más libros?" Es la prueba. Y "no, no más libros" es el caso base.
Recorrer un árbol de directorios es un buen ejemplo. Puede hacer algo similar para procesar una matriz. Aquí hay una función recursiva realmente simple que simplemente procesa una cadena, una matriz simple de cadenas o una matriz anidada de cadenas de cualquier profundidad, reemplazando instancias de ''hola'' con ''adiós'' en la cadena o los valores de la matriz o cualquier subarreglo:
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 cuándo salir porque, en algún momento, la "cosa" que está procesando no es una matriz. Por ejemplo, si llama a replaceHello (''hello''), devolverá ''adiós''. Si le envía una matriz de cadenas, aunque se llamará a sí mismo una vez por cada miembro de la matriz, entonces devuelva la matriz procesada.
Recursion utilizado para la 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;
}
La función sigue llamándose con el resultado del cálculo hasta que alcanza la constante Kaprekars, en la que devolverá la cantidad de veces que se hicieron los cálculos.
/ editar Para cualquiera que no conozca Kaprekars Constant, necesita una entrada de 4 dígitos con al menos dos dígitos distintos.
Si agrega un cierto valor (por ejemplo, "1") al ejemplo de Anthony Forloney, todo estaría 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.
}
}
Un ejemplo sería imprimir cada archivo en cualquier subdirectorio de un directorio determinado (si no tiene enlaces simbólicos dentro de estos directorios que puedan romper la función de alguna manera). Un pseudo-código de impresión de todos los archivos se ve así:
function printAllFiles($dir) {
foreach (getAllDirectories($dir) as $f) {
printAllFiles($f); // here is the recursive call
}
foreach (getAllFiles($dir) as $f) {
echo $f;
}
}
La idea es imprimir primero todos los subdirectorios y luego los archivos del directorio actual. Esta idea se aplica a todos los subdirectorios, y esa es la razón para llamar a esta función recursivamente para todos los subdirectorios.
Si quiere probar este ejemplo, debe verificar los directorios especiales . y .. , de lo contrario, se bloquea al llamar printAllFiles(".") todo el tiempo. Además, debe verificar qué imprimir y cuál es su directorio de trabajo actual (vea opendir() , getcwd() , ...).