Estoy perdido con la recursividad

Iniciado por Caster, 3 Octubre 2012, 19:35 PM

0 Miembros y 1 Visitante están viendo este tema.

Caster

Pues estoy leyendo sobre la recursividad y estoy totalmente perdido, no entiendo nada, dice que las llamadas a la funcion no se realizan en el momento de la llamada, sino que se acumulan hasta cumpla una condicion, y despues se ejecutan en orden inverso, es decir, que la primera llamada que se hizo es la ultima en ejecutarse?
Alguien amable podria explicarme esto de una forma algo mas facil, porque estoy muy perdido.

Gracias

EDITO: a ver, algo creo que voy entendiendo, de ejemplo me trae este codigo:

#include <stdio.h>

#define EOLN '\n'

void inverso(void);

int main() {
printf("Introduce una linea de texto debajo: \n");
inverso();
}

void inverso(void) {
char c;

if((c = getchar) != EOLN) inverso();
putchar(c);
return;
}


Antes de nada, no he compilado el codigo, voy a fiarme del libro, A ver si me explico y lo he entendido bien, este programa se supone que escribe el texto introducido al reves, ejemplo:

Citarhola - aloh

Cuaado tu introduces una letra, por ejemplo a, no la escribe, sino que vuelve a llamar a la funcion, es decir entra en bucle ejecutando la linea: if((c = getchar) != EOLN) inverso();hasta que la condicion del if se cumpla, entonces como segun el libro el orden de las llamdas es inverso, la primera letra que introduje sera la ultima en mostrarse, y asi con el resto de caracteres, estoy en lo cierto?

Espero haberlo entendido bien, porque es el ultimo punto de este tema y estoy deseando pasar de tema, pero no sin antes haberlo entendido todo perfectamente.

Gracias de nuevo

Stakewinner00

si basicamente es eso.

No se mucho de recursividad, pero algo e echo.

Yo tampoco lo entendia mucho hasta que practique con ello.

Yo directamente ya no me leo libros de programación sino que intento programar  ysi algo no lo se lo busco por google y luego lo implemento y ya se me queda grabado

leosansan

#2
CitarTe dejo como ejemplo la sucesión de fibonacci, que empieza con 1 y 1 y cada número es la suma de los dos anteriores:
1,1,2,3,5,8,13,21,34,55,.....:

#include <stdio.h>

long int fibonacci(long int  k);
int main(void)
{
   int i;
   for ( i=0; ;i++ )
   {
       if (fibonacci(i)>10000)  /*<==cuando supere este valor se para*/
               break;
       printf ("%ld    ",fibonacci(i));
   }
       printf ("%ld",fibonacci(i));
   return 0;
}

long int fibonacci(long int  k)
{
   if (k < 2)
       return 1;
   else
       return fibonacci(k - 1) + fibonacci(k - 2);
}
/*
         Por ejemplo, si llamo a  fibonacci(6) esto es lo que sucede:
                           6    <==llamada a fibonacci(6),este llama fibonacci(5)+fibonacci(4)
                                                   llamada a fibonacci(5),este llama fibonacci(4)+fibonacci(3)
                5 ...................... 4 <==
                                                   Y llamada a fibonacci(4),este llama fibonacci(3)+fibonacci(2)
                                                       y así sucesivamente.....fíjate que
           4.......3              3.........2      en cada llamada se resta uno hasta
                                                           que es uno.
       3.......2 2.....1       2.......1        1

   2.......1   1 1     1       1       1           1
   1   +   1 + 1+1  +  1 +     1  +    1    +      1 =8 =fibonacci(6)

Como dice tu libro "la primera llamada que se hizo,en este caso fibonacci(6), es la ultima en ejecutarse"*/


Otro ejemplo más simple que calcula el factorial:
#include <stdio.h>
long fact(int n)
{
    if (n==1)
        return 1;
    return n * fact (n-1);
}
main() {
int num;
printf("Introduzca un número entero: ");
scanf("%d", &num);
printf("Su factorial es: %ld\n", fact(num));
}
/*por ejemplo: num=6 ==>fact (6))

return:6*fact (5)
    return:6*5*fact (4)
         return:6*5*4*fact (3)
                return:6*5*4*3*fact (2)
                    return:6*5*4*3*2*fact (1)
                        return:6*5*4*3*2*1

PD:tú código no funciona.
Saludos!.

rir3760

Cita de: Caster en  3 Octubre 2012, 19:35 PMAntes de nada, no he compilado el codigo, voy a fiarme del libro
Al parecer al copiar el programa agregaste (de forma accidental, por supuesto) algunos errores o bien el libro no es de calidad. ¿Que libro estas leyendo?

Hay varias partes a modificar en la función "inverso":

* Faltan los paréntesis en la llamada a "getchar".
* El tipo de retorno de "getchar" es "int".
* Si "getchar" por alguna razón falla a partir de ese momento retorna "EOF" y como este valor es distinto de '\n' se entra en una recursion infinita.
* No es necesaria la sentencia "return;" al final de la función, esta retorna al encontrarse su llave de cierre '}'.

El programa con las correcciones:
#include <stdio.h>

void inverso(void);

int main(void)
{
   puts("Introduce una linea de texto debajo:");
   inverso();
   return 0;
}

void inverso(void)
{
   int c;
   
   if ((c = getchar()) == '\n')
      putchar('\n');
   else if (c != EOF){
      inverso();
      putchar(c);
   }
}


Un saludo
C retains the basic philosophy that programmers know what they are doing; it only requires that they state their intentions explicitly.
--
Kernighan & Ritchie, The C programming language

Caster

Gracias leosansan por los ejemplos, el de calcular el factorial es el primer ejemplo que viene en mi libro.


Cita de: rir3760 en  5 Octubre 2012, 17:32 PM
Al parecer al copiar el programa agregaste (de forma accidental, por supuesto) algunos errores o bien el libro no es de calidad. ¿Que libro estas leyendo?
Si, ha sido error mio al copiar el programa, aqui esta sin ningun fallo, exactamente como en el libro:

#include <stdio.h>

#define EOLN '\n'

void inverso(void);

int main() {
printf("Introduce una linea de texto debajo: \n");
inverso();
}

void inverso(void) {
char c;

if((c = getchar()) != EOLN) inverso();
putchar(c);
return;
}


Lo he compilado y funciona perfectamente,gracias por las correcciones, creo que ya he entendido mas o menos la recursividad y ademas en mi libro viene como apunte que no se suele utilizar mucho, y que problemas que se puede solucionar con la recursividad se puede hacer de manera mas facil de otras maneras, asi que tampoco me voy a parar mucho en ella.

Saludos