Comprender y programar recursividad# qué es concepto, ejemplo básico lenguajeC

[Pino1952]

Un muy buen día para todos.

Lo que me tiene dando vueltas hace 2 días es el tema de la recursividad, el enunciado del libro con el que estoy estudiando c pregunta ¿Qué hace el siguiente programa?, lo que hace es dar como resultado 180 que parecería que está multiplicando 18 * 10 (x * y) pero no hay ninguna multiplicación, por lo menos es lo que me parece.-
En definitiva necesitaría (si disponen de tiempo ) que me den teoría sobre el tema recursividad.-   

Código: [Seleccionar]

#include<stdio.h>

int misterio(int a, int b);
 
int main(void){
int x = 18, y=10, result=0;
result = misterio(x, y);
printf("\n misterio develado ==> %d", result);

return 0;
}

int misterio(int a, int b){
/* caso base*/
printf("\n a=%d == b=%d", a, b); /* Esto no está en el libro*/
if(b == 1){
return a;
}
else{
return a + misterio(a, b-1);
}
}
Un gran abrazo a todos.

Daniel     

[Alex Rodríguez]

Hola, si has leído algo en los foros habrás visto comentarios como que:

"La recursividad es difícil de entender"

"La recursividad es difícil de depurar"

"Hay programadores expertos que llevan muchos años programando y que no usan recursividad por su complejidad"

En todo esto hay parte de verdad, nosotros por ejemplo no la introducimos en los cursos básicos de aprendizaje de la programación por su complejidad.

Lo primero que deberías hacer si aún así quieres tratar de entenderla es ver un programa clásico y tratar de entender lo que hace. El programa ejemplo clásico de recursividad es el cálculo del factorial de un número. El factorial es el producto de ese número por todos sus antecesores hasta llegar a 1. Por ejemplo el factorial de 5 es 5*4*3*2*1 = 120 y el factorial de 3 es 3*2*1 = 6.

El factorial se puede calcular sin usar recursividad, o usándola, según se prefiera. El código recursivo es:

Código: [Seleccionar]



#include<stdio.h>
 
long factorial(int);
 
int main()
{
  int n;
  long f;
 
  printf("Ingrese el entero del que desea calcular el factorial\n");
  scanf("%d", &n);
 
  if (n < 0)
    printf("Los enteros negativos no estan permitidos.\n");
  else
  {
    f = factorial(n);
    printf("%d! = %ld\n", n, f);
  }
 
  return 0;
}
 
long factorial(int n)
{
  if (n == 0)
    return 1;
  else
    return(n * factorial(n-1));
}

En la recursividad tenemos estos factores importantes:

a) Una función se llama a sí misma

b) En cada llamada, tiene que haber algo que permita una evolución (si no estaríamos en una autollamada tipo bucle infinitio)

c) Tiene que existir una situación en la que ya no hay una nueva autollamada, sino un resultado o acción. Esta situación se denomina caso base y permite que se salga de la recursión.

En el ejemplo que hemos puesto la función es factorial.

El caso base es if (n==0) return 1;

La llamada recursiva (autollamada se produce en return(n* factorial (n-1));

La evolución se produce porque en cada llamada la función se llama con un entero una unidad inferior al entero con que se llamó anteriormente.

Por ejemplo si tú llamas factorial(4), cuando llega al return sel llama return (4*factorial(3)); , en la siguiente pasada se llama return (3*factorial(2)); ...

Pongamos por caso que se va a calcular factorial(3)

Empieza la ejecución de la función. Se comprueba si n vale cero y no es cierto (n vale 3), por lo que se produce que la función devuelve 3*(factorial(2));

Ahora se procede a calcular factorial (2) y nos devuelve 2*factorial(1) con lo cual en glogal tenemos 3*2*factorial(1)

Ahora se procede a calcular factorial(1) y nos devuelve 1*factorial(0) con lo cual en global tenemos 3*2*1*factorial(0)

Ahora se comprueba que n==0 por lo que la función devuelve 1 y nos queda 3*2*1*1 = 6

Si te fijas en realidad podríamos haber escrito if(n==1) return 1 y nos ahorramos hacer 1*1 que no sirve para mucho.

Con esto creo que podrías analizar el código y responder el ejercicio... a ver si puedes, coméntanos lo que te salga...

Saludos

[Pino1952]

Hola Alex.
Gracias por el aporte, si bien es muy esclarecedor todavía no me cae la ficha, considero que en menos de 1 semestre lo logro.-
Estoy con fe que lo voy a entender porque encontré un video (tengo visto como una decena sobre el tema) que lo explica de una manera por lo menos diferente.-   
Ni bien lo tenga claro se los comunico.-

Saludos.
Daniel

[Príncipe_Azul]

Hola, la recursividad, es muy similar a goto, que mucha gente usa goto como si fuese un bucle, y no es un bucle, goto ha sido creado en los viejos lenguajes de programación y cuando se inventó while, se prentendió no usar más goto como bucle.

No se C, pero Python tiene un limitador de llamadas, que si se supera, el programa se cierra, no sé si esto sucede en C, puede que si en casos muy exigentes.

De todas maneras, creo que un bucle while o for sería mejor que llamadas a una misma función.

Saludos!

[Pino1952]

Hola.

De todas maneras, creo que un bucle while o for sería mejor que llamadas a una misma función.

Estoy leyendo y escuchando mucho sobre el tema y realmente en teoría parece interesante pero en la práctica como dices  es más usada la forma interactiva que la recursiva, de cualquier manera le voy a dedicar un tiempito más para saber del todo como funciona y así lo tengo incorporado.- 

Saludos.
Daniel