Dúvida sobre recursão

Sarcofagobra
(usa Outra)

Enviado em 22/12/2011 - 22:52h

Pessoal tô com muita dificuldade de entender recursão, eu pulei essa parte no meu curso e só cheguei a fazer um programinha de fatorial, se me pedirem pra fazer um programa pra imprimir de 1 a 100 usando recursão eu não tenho a mínima ideia...

me expliquem uma coisa,


na linha 09 onde fica armazenado o valor que é multiplicado?

LINK DO CÓDIGO: http://codepad.org/NTbHi0Jh

return num *fatorial(num-1);


por exemplo o numero passado é 4


ai nessa linha vai ficar 4 * 3 = 12


onde vai ficar esse 12 pra ele ser multiplicado por 2 (3-1)?
e da o resultado de 24?

EnzoFerber
(usa FreeBSD)

Enviado em 22/12/2011 - 23:41h

Olá!

Cara, recursão, é um recurso bem legal, se usado com sabedoria ;)
Pode ser muito útil, ou muito desagradável (Seg. Fault, Illegal Inst.)

Seguinte, no caso do fatoria.

int fat ( int n ) {

     return ( n < 2 ) ? 1 : n * fat(n -1 );

}

 

Se você chamar a função assim:

d = fat(4);

 

O que o computador fará vai ser:

fat(4):

   4 é menor que 2? 

       não: então, 4 (n) * fat(3)

fat(3):

   3 é menor que 2?

       não: então, 3 * fat(2)

fat(2):

   2 é menor que 2?

       não: então, 2 * fat(1)

fat(1):

   1 é menor que 2?

       sim: então, retorna 1

 

Nesse retorno da ultima função ( fat(1) ), todas as outras, que estavam encadeadas, vão retornar também. O computador encadeou as funções em níveis, sendo o nível 1 o nível de chamada:

1. fat(4)

2. 4 * fat(3)

3. 3 * fat(2)

4. 2 * fat(1)

5. fat(1) retorna 1

 

Quanod retornar o fat(1), o computador vai retroceder até o nível que chamou a função, ou seja:

5. fat(1) -> retornou 1

4. 2 * fat(1) -> fat(1) retornou 1, então nivel 4 = retorna 1 * 2

3. 3 * fat(2) -> fat(2) retornou 1 * 2, então nivel 3 = retorna 1 * 2 * 3

2. 4 * fat(3) -> fat(3) retornou 1 * 2 * 3, então nivel 2 = 1 * 2 * 3 * 4

1. fat(4) -> retorna 1 * 2 * 3 * 4 = [ 24 ]

 

Entendeu?
Se não, posta denovo com sua dúvida,

Espero ter ajudado,
Enzo Ferber
[]'s

EnzoFerber
(usa FreeBSD)

Enviado em 22/12/2011 - 23:48h

2 exemplos pra você de recursividade:

1. Fatorial. (int fat())
2. Fibonnaci (int fib())

http://codepad.org/sosR9UrI

EnzoFerber
(usa FreeBSD)

Enviado em 23/12/2011 - 00:00h

http://codepad.org/7nef7D9H

Em níveis pra você ;)

// Enzo Ferber - Viva O Linux



#include <stdio.h>

#include <stdlib.h>



int fat ( int n )

{

    register int i;

    if ( n < 2 ) {

        for ( i = 0; i < n; i++ ) printf ( "  " );

        printf ( "# fat(1) =  1\n" ); 

        return 1;

    }

    else {

        for ( i = 0; i < n; i++ ) printf ( "  ");

        printf ( "# fat(%d) = %d * fat(%d)\n", n, n, n - 1);

        return n * fat(n-1);

    }

}



int main ( void )

{

    fat(5);

    return 0;

} 

    

 

Output:

          # fat(5) = 5 * fat(4)

        # fat(4) = 4 * fat(3)

      # fat(3) = 3 * fat(2)

    # fat(2) = 2 * fat(1)

  # fat(1) =  1

 

[]'s

Sarcofagobra
(usa Outra)

Enviado em 24/12/2011 - 18:43h

int fat ( int n ) {
return ( n < 2 ) ? 1 : n * fat(n -1 );
}

pow, vc frag amuito kra, vlws pela ajuda mais ainda tenho uma dúvida,
pq a a função não retorna fazendo imprimir na tela 12, 24...

como seria pra mostrar por exemplo assim: 4! = 12 - 24?

EnzoFerber
(usa FreeBSD)

Enviado em 10/01/2012 - 10:26h

Perdoe a demora, estava viajando com a esposa e família. :)
Férias faz bem pra todo mundo, né não?!

// Enzo Ferber - Viva O Linux

 

#include <stdio.h>

#include <stdlib.h>

 

int fat ( int n )

{

    register int i;

    

    if ( n < 2 ) {

        for ( i = 0; i < n; i++ ) printf ( "  " );

        printf ( "# fat(1) =  1\n" );

        return  1;

    }

    else {

        for ( i = 0; i < n; i++ ) printf ( "  ");

        printf ( "# fat(%d) = %d * %d\n", n, n, nfat(n-1));

        return n * fat(n-1);

    }

}



int nfat ( int n )

{

    return ( n < 2 ) ? 1 : n * nfat(n-1);

}

 

int main ( void )

{

    printf ("\n# Resultado: %d\n", fat(5));

    return 0;

}

 

Output:

          # fat(5) = 5 * 24

        # fat(4) = 4 * 6

      # fat(3) = 3 * 2

    # fat(2) = 2 * 1

  # fat(1) =  1



# Resultado: 120

 

Isso ai que você queria?


Atenciosamente,
Enzo Ferber
[]'s