Recursividad

Clase 23 de 27 • Curso de Programación Estructurada

Resumen

En C, las funciones pueden llamarse a sí mismas.
Si una expresión en el cuerpo de una función llama a la propia función, se dice que ésta es recursiva.
La recursividad es el proceso de definir algo en términos de sí mismo y a veces se llama definición circular.

Ervic Perez Mendoza

student•

Recursividad

Un método recursivo es un método que se llama así mismo. Una de las tareas clásicas que pueden ser resueltas fácilmente por recursión es el calculo del factorial de un numero. _ En matemáticas, el termino factorial se refiere al producto de todos los enteros positivos que son menores o iguales que un número entero específico no negativo (n). El factorial de n se escribe como n!. _ Por ejemplo:

5! = 5 * 4 * 3 * 2 * 1 = 120 _ A pesar de que ejemplo de arriba es fácil de entender se están omitiendo algunos pasos que nuestro programa realiza para encontrar el factorial del número 5, dichos pasos son los siguientes: _ Factorial(5)

return 5 * Factorial(4)

return 5 * (return 4 * Factorial(3) )

Return 5 * (return 4 * (return 3 * Factorial(2) ) )

Return 5 * (return 4 * (return 3 * (return 2 * Factorial(1) ) ) ) _ …pero Fact(1) retorna 1, así que rastreamos hacia atrás… _ Return 5 * (return 4 * (return 3 * (return 2 * 1) ) )

Return 5 * (return 4 * (return 3 * (return 2) ) )

Return 5 * (return 4 * (return 3 * 2 ) )

Return 5 * (return 4 * return(6) )

Return 5 * (return 24)

Return 5 * 24

Return 120

120 _ Ahora supongamos que se nos pide encontrar el factorial del número 3, se podría pensar que la tarea a realizar solo seria: Factorial(3) = 3 * Factorial(2) = 3 * 2 * Factorial(1) = 6. En esta explicación estaríamos omitiendo algunos pasos que realmente el programa hace; por lo que explicación correcta seria: Factorial(3) = 3 * Factorial(2) Resolver para Factorial(2): 2 * Factorial(1) Resolver para el Factorial (1) = 1 Entonces, Factorial(1) = 1 _ Entonces rastrearíamos hacia atrás: Factorial(2) = 2 * 1 = 2 Rastrear de nuevo: Factorial(3) = 3 * 2 = 6 _ Si esta explicación es confusa o incorrecta favor de comentar, estuve investigando este tema y la mayoría de los ejemplos expuestos anteriormente los tome de la aplicación llamada, "Solo Learn".

Wilson Alexander Caal Pacay

student•

Genial, Solo Learn es super :)

Juan Manuel Caro González

student•

Amigo me quedé cuando dices "así que rastreamos hacia atrás". Básicamente tengo dos dudas con esta clase:

En el primer return del if los resultados se van almacenando en la variable result? Me quedé cuando llega return 1; y dice Dani: “ahora se regresa capa por capa por capa”. Siguiendo la lógica de lo aprendido hasta esta clase, lo que debería ocurrir después de llegar a return 1 es que la función factorial finaliza y ese “1” de resultado se almacena en la variable result de la función main. No entendí cómo se devuelve por las capas y como se llega al resultado de 120, ni tampoco entendí entonces en qué momento se sale de la función factorial.

Walker Fernando Manrique Chalco

student•

En la recursividad una funcion se llama a si misma hasta que llegue al caso base. Pero luego de que llega al caso base va de regreso, es decir llega al final, regresa hacia donde lo llamo la ultima vez y asi sucesivamente hasta que llegue al comienzo. La recursividad entonces va de ida y vuelta.

Ricardo Exequiel De Angelis

student•

Sencilla y buena definición

mauricio garcia

student•

esta excelente esta imagen! gracias

Manuel Alejandro Aguilar Téllez Girón

student•

Hay diferencias sutiles entre recursividad e iteración.

Algunas de ellas por ejemplo es que la iteración incluye, una inicialización, una condición y un incremento o decremento. La recursividad por sí misma sólo es un bucle que regresa siempre al caso base (condición), y es ahí cuando viene una segunda diferencia, en una iteración nosotros estamos obligados a poner una condición para que sea cumplida, en la recursividad no, la diferencia es que (aparte de que ya está definida [caso base]) si no la ponemos llegará a un bucle infinito, a lo que lleva a una tercera diferencia, la iteración hace que tu CPU cicle una y otra vez, la recursividad puede llegar a crashear totalmente tu computadora. La recursividad es más lenta en ejecución que la iteración, esta se comporta por medio de stacks, la iteración no, aparte las iteraciones hacen más largo tu código que la recursividad.

Pablo Reyes Abarca

student•

que ejemplos practicos podrias decirnos para que quede mas claro, entre en duda? 😦
gracias

Manuel Alejandro Aguilar Téllez Girón

student•

 1 #include <stdio.h>
  2 
  3 int n_factorial(int a){
  4   if (a > 1){
  5     return a *  n_factorial(a - 1); //aqui se esta llamando a si misma
  6   } else {
  7     printf("Terminamos\n");//aqui termina el loop porque a = 1
  8     return 1;
  9   }
 10 }

Como te puedes dar cuenta, nosotros en el ejemplo tuvimos que introducir una condición, porque de lo contrario entraríamos en un bucle infinito, la condición en este caso comprende todas las líneas que componen a la función n_factorial, aunque bien simplemente pudimos haber dejado la función así. Otro asunto es que no tenemos tantas líneas de código como tendríamos si ese bucle lo introducimos dentro de una main por ejemplo. Otra diferencia evidente es que recursividad sólo se puede en funciones, no en condicionales.

Con el tema de los stacks, imagina que entra en la función, hace todo el recorrido y lleva ya una información, en este caso que es la que regresa con return, cuando llega a la línea donde se llama a sí misma, vuelve a entrar con esa información y sale con otra, a eso me refiero con stacks, así hasta que la condición nos ayude a salir de ese estaqueamiento (xD).

Ahora veamos uno de iteración:

for (int i = 0; i < 10 ; i++);

En la segunda parte de ese for introducimos una condición que es obligatoria porque de lo contrario nuestro bucle for, no “jalaría”, digamos que ahora entramos en un bucle infinito:

for (int i = 0; i <= 10; i--);

Ahí haríamos ciclar nuestro CPU una y otra vez entrando en esa iteración hasta que lo paremos con un control + C desde el teclado, ese bloque de iteración va forzosamente dentro de una función no pude ir afuera, no puede pasar eso:

#include <stdio.h>

for (int i = 0; i > 0; i--) {
	printf("hola mundo \n");
}

int main() {
	//eso no se puede xD
}

Wilson Perez

student•

Una pequeña explicación gráfica de recursividad.

carlos Francisco Pinto Guerrero

student•

Como no había reto decidí hacer uno de los retos del principio que era implementar la sucesión de fibonacci

<#include <stdlib.h>
#include <stdio.h>

int fibonacci(int number){
    if (number > 2){
       return fibonacci(number-1) + fibonacci(number-2);
    }
    else {
        return 1;
    }
}

int main(){
    int result,number;
    printf("Sucesion de fibonacci\n");
    printf("Ingrese un numero para la sucesion ");
    scanf("%i", &number);

    result = fibonacci(number);
    printf("El fibonacci de %i: %i",number,result);
    return 0;
}
>

Jecsham Castillo

student•

Buen ejemplo

Wilson Perez

student•

Un poco de teoría interesante sobre recursividad. Recursión es una de las ideas centrales de ciencia de computación. Resolver un problema mediante recursión significa que la solución depende de las soluciones de pequeñas instancias del mismo problema. Un algoritmo recursivo es un algoritmo que expresa la solución de un problema en términos de una llamada a sí mismo. La llamada a sí mismo se conoce como llamada recursiva o recurrente. Crear una subrutina recursiva requiere principalmente la definición de un "caso base", y entonces definir reglas para subdividir casos más complejos en el caso base. Para una subrutina recursiva es esencial que con cada llamada recursiva, el problema se reduzca de forma que al final llegue al caso base. Generalmente, si la primera llamada al subprograma se plantea sobre un problema de tamaño u orden N, cada nueva ejecución recurrente del mismo se planteará sobre problemas, de igual naturaleza que el original, pero de un tamaño menor que N. De esta forma, al ir reduciendo progresivamente la complejidad del problema que resolver, llegará un momento en que su resolución sea más o menos trivial (o, al menos, suficientemente manejable como para resolverlo de forma no recursiva). En esa situación diremos que estamos ante un caso base de la recursividad.

Las claves para construir un subprograma recurrente son: • Cada llamada recurrente se debería definir sobre un problema de menor complejidad (algo más fácil de resolver). • Ha de existir al menos un caso base para evitar que la recurrencia sea infinita.

A modo de ilustración: Si se encuentra una palabra desconocida en un libro, el lector puede anotar la página actual en un papel y ponerlo en una pila (hasta entonces vacía). El lector consulta la palabra en otro artículo y, de nuevo, descubre otra palabra desconocida, la anota y la pone en la pila, y así sucesivamente. Llega un momento que el lector lee un artículo que donde todas las palabras son conocidas. El lector retorna entonces a la última página y continua la lectura desde ahí, y así hasta que se retira la última nota de la pila retornando entonces al libro original. Este modus operandi es recursivo.

La recursividad tiene sus inconvenientes. Invoca de manera repetida al mecanismo, y por consecuencia, la sobrecarga de llamadas a la función. Esto puede ser costoso tanto en tiempo de proceso, como en espacio de memoria. Cada llamada recursiva crea una copia de la función, esto puede consumir una considerable cantidad de memoria. Mientras que utilizando estructuras de iteracción, esta ocurre dentro de una función, de manera que evita la sobrecarga de llamadas repetidas a una función y la asignación adicional de memoria. Entonces ¿Por qué elegir la recursividad? Cualquier problema que se puede resolver de manera recursiva también se puede resolver de manera iteractiva. Por lo general, el método de recursividad se elige por encima de uno de iteracción , cuando el método de recursividad refleja de manera mas natural el problema y genera un programa que es mas fácil de entender y depurar. Otra razón para elegir una solución recursiva es que la solución iterativa no es obvia.

Usuario anónimo

user•

🤔 La recursividad o recursión permite que las funciones que se llamen a sí mismas, evitando el uso de iteradores.

Luis Angel Rojas Estevez

student•

Espero que la siguiente explicación libre de dudas a los futuros estudiantes:

La recursividad funciona de esta forma 1.- Buscamos el factorial de 5, por lo tanto n es igual a 5. 2.- A la función factorial le pasamos como parámetro n, es decir, 5. 3.- Entramos a la condición if; ¿n es mayor que 1?, resp: si, numero vale 5, por lo tanto 5 > 1 4.- Entreamos a recursivida; n que multiplica a la función factorial de n menos 1, es decir, aquí hay una interrogante 5 * 4!, AHORA n VALE 4 POR LO TANTO EMPIEZA LA RECURSIVIDAD. 5.-VOLVEMOS A ENTRAR EN LA FUNCIÓN FACTORIAL, hace el mismo proceso que con 5, pero con n-1, por lo que quedaría de la siguiente forma: 1.- n = 5 * 4!, AHORA n VALE 4 2.- n = 4 * 3!, AHORA n VALE 3 3.- n = 3 * 2!, AHORA n VALE 2 4.- n = 2 * 1!, AHORA n VALE 1 5.- n = 1* 0!, AHORA n VALE 0. Aquí es donde hace la ultima llamada a si mismo.

6.- Entramos a if() nuevamente, if(n > 1), en este instante n vale 0, por lo tanto, no cumple la condición y devuelve 1.

De esta manera resolvemos las demás incógnitas, Algo que es importante mencionar es, como factorial es una función, un espacio reservado en memoria, guarda las incógnitas pasadas, esto debido a que no a devuelto ningún valor.

Entonces:

7.- Ya sabemos que el factorial de cero es igual a 1, por lo tanto, vamos de abajo hacia arriba, por así decirlo:

         5.- 1 * 0!, y como 0! = 1, entonces 1 * 1 = 1, AHORA n vale 1
         4.- 2 * 1!, y como 1! = 1, entonces 2 * 1 = 2, AHORA n vale 2 
         3.- 3 * 2!, y como 2! = 2, entonces 3 * 2 = 6, AHORA n vale 6 
         2.- 4 * 3!, y como 3! = 6, entonces 4 * 6 = 24, AHORA n vale 24 
         1.- 5 * 4!, y como 4! = 24, entonces 5 * 24 = 120, AHORA n vale 120

Así es como llegamos al factorial de 5, debemos tomar en cuenta cual es nuestro caso base y cual nuestro caso general por ello la condicional if(n > 1), esto debido a que sabemos que el factorial de 0 es 1 y el factorial de un numero distinto a 0 es el número multiplicado por la resta del mismo número menos uno.

8.- Si queremos mostramos los resultados, podemos usar un ciclo for(), esto es posible debido a que solo imprime el resultado de la función cuando le pasamos como parámetro el numero con la iteracion, es decir, se cuenta de 0 a 5 y factorial tiene como parámetro i:

     factorial(i)
        --> Cuando i es igual a 0, factorial tiene como parámetro 0
        --> Cuando i es igual a 1, factorial tiene como parámetro 1
        --> Cuando i es igual a 2, factorial tiene como parámetro 2

Espero les sirva, si esta mal explicado porfavor corrijanlo.

Beto Toro

student•

Parcero no entendí porque se devuelve y por que colocas el signo ( " ! ", que entiendo que significa " diferente " ) después de los números en la primera foto.

Cristian Blandón

student•

@BetoToro Ten en cuenta que las imágenes no tienen "código", sino explicaciones. ! significa factorial en matemáticas.

¡Saludos!

Angie Gomez

student•

Al principio no me quedó muy claro y encontré éste tutorial por youtube, que me despejó un poco más las dudas: https://www.youtube.com/watch?v=vjjw8Xp8rII Creo que en una de las imágenes del video se resume todo:

para que el primer return pueda dar un resultado debe llevarse a cabo la función varias veces hasta llegar a la condición donde n es igual a uno, de allí se devuelve y otorga el resultado final que es igual a 120

jose ortiz

student•

y como para que usariamos este concepto? algun ejemplo de buen uso de recursividad en alguna aplicacion?

Starling Germosen

student•

Buena pregunta, yo no tengo idea, estoy pendiente de este post,

Héctor Daniel Vega Quiñones

teacher•

La recursividad al ser un tema abstracto pueden no encontrarse aplicaciones de forma inmediata, sino que requieren de un análisis más detallado. En estos casos sus aplicaciones están más orientadas a la ingeniería de datos para encontrar datos específicos o incluso en la inteligencia artificial.

Oriana Suljeis Posada Molina

student•

Alguien me puede explicar que función cumple return n en esta parte, return n * factorial(n-1); me confunde si en ese punto return n vale 1 ´por el return 1; del else. Y en que momento se cumple la multiplicación.

else
  {
    printf(&quot;\nn es igual a 1, termina la recursividad \n&quot;);
    return 1;
  }```

Adan Natanael Segura Galicia

student•

la multiplicación se cumple en ese mismo momento con n * factorial(n-1). Ej. si tu ingresas 4 pasa lo siguiente n ----> 4 4 * factorial(n-1) -----> (el (n-1) se convierte en tu nueva n ---> 3) quedando: 4 * 3 * factorial(n-1) -----> ((n-1) ---> 2) 4 * 3 * 2 * factorial(n-1) -----> ((n-1) ---> 1) ---> En este momento entra al else quedando: 4 * 3 * 2 *1 -----> siendo esta la operación que se realiza utilizando la función recursiva.

Ojala me haya dado a entender. Saludos :)

Carlos Arturo Murcia Andrade

student•

Reto personal: Número de Fibonacci recursivo.

#include <stdio.h>
#include <stdlib.h>

int fibonacciNumber (int n)
{
    if (n == 0)
        return 0;
    else if (n == 1)
        return 1;
    else
        return fibonacciNumber(n-1) + fibonacciNumber (n-2);
}

int main()
{
    printf("Sucesion de Fibonacci recursiva. \n");

    int fibo, result;

    printf("Ingresa el numero de Fibonacci que deseas obtener (indice): ");
    scanf("%i", &fibo);

    result = fibonacciNumber(fibo);

    printf("El numero de Fibonacci en el indice %i es: %i\n", fibo, result);

    return 0;
}

Wilson Fernando Antury Torres

student•

Excelente, siempre he luchado con éste concepto, solo faltaba entender que así como se llaman varias veces la misma función cuando termina hace lo mismo hacia atrás, devolviendo los resultados, uno tras otro. Ahora si ya lo entendí.

Luis Franco

student•

Este es ejercicio similar que el del video y otra manera de hacer un ejercicio que ya hemos hecho (El de sacar la potencia).

#include <stdio.h>
#include <stdlib.h>

int potencia(int laBase, int suExponente)
{
    if(suExponente < 1)
    {
        return 1;
    }
    else
    {
        return laBase * potencia(laBase, suExponente - 1);
    }
}

int main()
{
    int n, pot;

    printf("Sacar la potencia de un numero\n\n");

    printf("Ingrese la base: ");
    scanf("%i", &n);

    printf("Ingrese la potencia: ");
    scanf("%i", &pot);

    printf("\nEl resultado de %i^%i es: %i", n, pot, potencia(n, pot));

    return 0;
}

Mauricio Carrasco

student•

Un calculador de factoriales:

#include <stdio.h>
#include <stdlib.h>

int factorial(int n)
{
    printf("\nEntra a la funcion factorial, n vale: %i \n", n);

    if(n > 1)
    {
        printf("La funcion se llamara a si misma otra vez\n");
        return n * factorial(n -1);
    }
    else
    {
        printf("Cuando n vale 1 se acaba la recursividad\n");
        return 1;
    }
}




int main()
{
    printf("Recursividad \n\n");

    printf("Calculador de factorial\n\n");

    int num;
    printf("Ingrese el factorial que quiere hallar: ");
    scanf(" %i", &num);

    printf("\n\nPROCESO:\n");
    int resultado = factorial(num);

    printf("\n\nRESULTADO:\n");
    printf("\nEl factorial de %i es: %i", num, resultado);

    printf("\n\n");
    printf("FINALIZO EL PROGRAMA");
    return 0;
}

Juan Manuel Caro González

student•

Tengo dos dudas:

En el primer return del if los resultados se van almacenando en la variable result?
Me quedé cuando llega return 1; y dice Dani: "ahora se regresa capa por capa por capa". Siguiendo la lógica de lo aprendido hasta esta clase, lo que debería ocurrir después de llegar a return 1 es que la función factorial finaliza y ese "1" de resultado se almacena en la variable result de la función main. No entendí cómo se devuelve por las capas y como se llega al resultado de 120, ni tampoco entendí entonces en qué momento se sale de la función factorial.

Fernanda Vieira Jófili

student•

Hola @jmcaro!

En el return del IF, es como si esto pasara: Para Factorial(5), es decir, n = 5.

return 5 * factorial (n-1)

Ahora la función es llamada de nuevo. El parámetro ahora es n - 1 = 5 - 1 = 4.

Por lo tanto, pausa el factorial del primer factor (5) y calcula el del segundo factor (4). Y cuando se trata del retorno del segundo factor, debe calcular el factorial de (3) ... Y así continúa, hasta que el factor (1) que no vuelve a llamar a la función factorial, ya tiene un valor específico para el retorno (return 1)

Por lo tanto, con el último retorno definido, retrocede retorno por retorno y reemplazará los valores ya calculados.

Sabiendo que el orden de los retornos, cada vez que se llamaba a la función era este: 1º return

return 5 * factorial ( 4)

2º return

return 4 * factorial (3)

3º return

return 3 * factorial (2)

4º return

return 2 * factorial (1)

5º return

return 1

Comienzas del último al primero. Por lo tanto, reemplazando el quinto retorno (el último), tenemos: 5º return

return 1

4º return

return 2 * 1
2

Pues ya sabemos que el factorial (1) = 1. Así, sabemos que factorial (2) = 2. Podemos reemplazarlo en el 3º return:

3º return

return 3 * 2
6

2º return

return 4 * 6
24

1º return

return 5 * 24
120

Y listo! Tienes el factorial de 5 :) Ahora si el valor es pasado a variable result de la función main. Espero que te ayude ;)

Francisco Javier garay velazquez

student•

¿Dónde encuentro el video del oso y el tigre, de recursividad?

Omar Daniel Centeno

student•

Aquí te lo dejo :D

Francisco Javier garay velazquez

student•

Muchas gracias

Camilo Arias Céspedes

student•

¿En terminos de practicidad, es mejor hacer una función recursiva, o generar una sola función con un ciclo?, por temas de memoria y procesamiento de datos, ¿que es más optimo?

JESUS ALBERTO CARREÑO MARTINEZ

student•

Hola Para esto te recomiendo investigar el tema de Big O Notation, lo cual permite ver el crecimiento de una función, lo cual se traduce en datos, capacidad de computo etc

Las funciones recursivas tienen una notación de 2**n, es decir, que crecerán exponencialmente, lo cual toma mas tiempo de resolver

En este gráfica puedes ver mejor el crecimiento de cada funcion

JESUS ALBERTO CARREÑO MARTINEZ

student•

Te recomiendo ver la clase del profesor Aroesti https://platzi.com/clases/1775-poo-python/25261-notacion-asintotica/ Saludos

Mauricio Carrasco

student•

He estado probando hasta donde se podia hallar el factorial del programa y descubri que se rompe del factorial de 13 en adelante. ¿Alguien sabe porque pasa esto?

Este es mi codigo

#include <stdio.h>
#include <stdlib.h>

int resultado_factorial;

int factorial(int n)
{
    printf("\nEntra a la funcion factorial, n vale: %i \n", n);


    if(n > 1)
    {
        printf("La funcion se llamara a si misma otra vez\n");
        return n * factorial(n -1);

    }
    else
    {
        printf("Cuando n vale 1 se acaba la recursividad\n");
        return 1;
    }
}




int main()
{
    printf("Recursividad \n\n");

    printf("Calculador de factorial\n\n");

    int num;
    printf("Ingrese el factorial que quiere hallar: ");
    scanf(" %i", &num);

    printf("\n\nEXPLICACION DE LA RECURSIVIDAD:\n");
    int resultado = factorial(num);

    printf("\n\nRESULTADO:\n");
    printf("\nEl factorial de %i es: %i", num, resultado);

    printf("\n\n");
    printf("FINALIZO EL PROGRAMA");
    return 0;
}

El resultado de mi codigo con factorial de 13

El resultado real

Patrick Jhonatan Hernandez Blanco

student•

Por el tipo de dato: -32,768 a 32,767 o -2,147,483,648 a 2,147,483,647

Jorge Cruz Perez

student•

Si habria que usar un long, saludos :)

Joel Vicente Nieto Gómez

student•

Como se calcula el Time Complexity y el Space Complexity de un código recursivo?