Funções Recursivas

[Manwë Súlimo]

Pessoal, o que é exatamente uma funçào recursiva?? o que significa recursividade...??

desculpem minha ignorancia...

alguém pode me ajudar???

até mais

[rodfraga]

Uma função recursiva, é uma função que chama a si mesma para devolver resultados. Segundo os Deitel, em C++ Como Programar, recursão é um assunto abordado até o final de um curso de Ciências da Computação, pois pode se tornar complexo.

Um exemplo de uma função recursiva, é uma que calcula o fatorial de um número. Exemplo em C:

unsigned long fatorial( unsigned long n )
{
    if ( n <= 1 )
        return 1;
    else
        return n * fatorial( n - 1 );
}

O fatorial de n é igual a n vezes o fatorial de n - 1, para isso pode-se usar chamadas recursivas para calcular o valor fatorial de n, como a função ali em cima.

[Manwë Súlimo]

então função recursiva é uma funçào que chama ela mesma até que determinada comdição seja alcançada???

como se fosse um loop??

Valeu Aragorn...

OBS.: você sabe quem é Manwe Súlimo??

até mais

[rodfraga]

Na verdade, deve haver uma hora em que a função não chame a si mesma, pois seria um loop infinito.

Sim, seria como um loop, e a condição do if ali seria a condição final do loop. Porém, devem haver outros modos de fazer isso.

Ah, deve ser algo de SdA não?

[Manwë Súlimo]

Valeu Aragorn, vou procurar mais sobre funções recursivas então.. até mais

e valeu

Ah na verdade é do Silmarillion, que conta a origem da terra média, ele é um deus ou semi deus da Terra Média

até mais

[rodfraga]

Não há de que.

Legal, eu não cheguei a ler a biblioteca Tolkien toda ainda.

[kandrade]

toda função recursiva tem que ter sua condição de parada tb chamada de solução trivial da recursividade......

no caso do exemplo de nosso amigo Aragon13 a função chama ela mesma até que n seja 1.......apartir dai ela vai retornando os valores até completar todas as funções pendentes........

ou seja.......se você não tem uma condição de parada o programa da estouro de pilha pois fica com uma enorme quantidade de função com a solução pendente na memória........

por isso......nem sempre a recursão é a melhor solução.......

te+........

[rodfraga]

Recursão em excesso causa o overhead o que é um problema que os Deitel adoram dizer que é o principal a ser levado em conta!

A idéia principal da recursão é transformar um problema, em um duas partes lógicas:

A que a função pode resolver e uma mais simples que o problema total, então a função chama a si mesma, passando o problema menor. Ela vai quebrando o problema até que ele se forme num problema tão simples que a função pode resolver e não precisa chamar a si mesma mais.

[gladiador]

/* em alguns de meus estudos descobri !!!

Regras :

Saber quando parar

Qualquer função recursiva de verificar se o procedimento foi completado antes da nova chamada recursiva

recursão nada mais é que a repetiçãp consecutiva do primeiro passo até que o procedimento seja completado

dividir o procedimento em procedimento menores

só existe recursão se o problema pode ser dividido em problemas menores e identicos

É muito usada em foruns utilizam 90% recursão

Cuidado

Códigos recursivos quando bugados geram falhas de execução perigosas e consequentemente estouros de pilha na memória da máquina.

*/

[== Douplus ==]

  
unsigned long fatorial( unsigned long n )
{
   if ( n <= 1 )
       return 1;
   else
       return n * fatorial( n - 1 );
} 

Sua função não especifica o tipo de retorno e nem o tipo de argumento a ser recebido, nesse caso teria que ser unsigned long int(você não declarou o int). Agora... Um fato curioso que descobri quando fiz um teste com os compiladores DJGPP e Dev-C++. Veja esse programa que fiz:

#include <iostream>
   using std::cout;
   
int main(void)
{
   cout<<" Tamanho     \t Valor\n\n";
   cout<<"short int    \t   "<<sizeof(short int)<<'\n';
   cout<<"  int        \t   "<<sizeof(int)<<'\n';
   cout<<"long int     \t   "<<sizeof(long int)<<'\n';
   cout<<"long long int\t   "<<sizeof(long long int)<<'\n';
   cout<<"  float      \t   "<<sizeof(float)<<'\n';
   cout<<"  double     \t   "<<sizeof(double)<<'\n';
   cout<<"long double  \t  "<<sizeof(long double)<<'\n';
   
   return 0;
}

Agora vejam a saída após compilado no DJGPP ou Dev-C++(é a mesma):

 Tamanho         Valor

short int              2
  int                    4
long int               4
long long int        8
  float                 4
 double               8
long double        12

Observem que tanto variáveis int como long int ocupam um espaço de memória com o mesmo tamanho. Será que é por convenção que int é equivalente a long int em questão de tamanho de espaço utilizado?

[rodfraga]

Quanto ao espaço ocupado, isso muda de máquina para máquina ( assim como a capacidade de cada tipo ).

Quanto a minha função, sim, ela especifica valor do retorno e também o do argumento recebido. long é uma abreviação de long int.

Aliás, a função nem é minha, eu tirei do C++ Como Programar, dos Deitel, então eu acho que não está errada.