Utilizando técnicas recursivas em C e C++

Um procedimento é chamado de recursivo quando faz referência a si mesmo. Neste pequeno artigo vou mostrar como fazer uso de uma função recursiva.

[ Hits: 57.019 ]

Por: Carlos Alberto em 23/09/2004


O que é recursividade?



A recursividade ocorre quando um algoritmo ou método chama a si mesmo.

Por exemplo: Imaginemos um algoritmo simples para calcular o fatorial de um número.

int fatorial(int x) {

    int i = x;

    while ( x > 1 ) {
        x = x * (x - 1);
        i = i - 1;
    }

    return x;
}

Agora vamos pensar como se calcula o fatorial de um número:
  • O fatorial de zero é, por definição, 1.
  • O fatorial de 1 é 1.
  • O fatorial de 5 é 5x4x3x2x1.

Agora qual é o fatorial de N?
Olhando a definição, podemos dizer que o fatorial de N é:

1 se N < 2;
N * (N-1)!

Viram a recursividade?

Página anterior     Próxima página

Páginas do artigo
   1. Introdução
   2. O que é recursividade?
   3. Versão recursiva da função fatorial
   4. Conclusão
Outros artigos deste autor
Nenhum artigo encontrado.
Leitura recomendada

Ponteiros - Saindo de Pesadelos

Algum humor e C++ Design Patterns (parte 2)

Bug afeta todas as distros

Como funcionam os alocadores de memória do STD C?

Mapear objetos em C

  
Comentários
[1] Comentário enviado por Ragen em 23/09/2004 - 09:40h

citando:
------------
Viram como a função ficou bem mais simples?

Explicando:
O if testa se o argumento passado para a função é menor que dois e em caso afirmativo a função retorna 1 e acaba.

Se o o argumento não for menor que dois, a função chama a ela própria com o argumento (x) decrementado de uma unidade e multiplica o valor de retorno por x.
-------

Realmente a funcao ficou menor, porém sabe-se que funcoes recursivas só devem ser usadas em pontos EXTREMAMENTE criticos...

Primeiro por que funcoes recursivas comem memoria, segundo por que torna seu programa extremamente lento, e terceiro por que pode deixa-lo instavel...

Mas ficou muito bem colocado seu artigo, bastante didatico

[]'s

Ragen

[2] Comentário enviado por tagallo em 23/09/2004 - 10:07h

realmente é um recurso bem importante esse... mas os programadores iniciantes tem que tomar cuidado, pois o seu mau uso pode levar a muitos bugs "fodas"... vale lembrar tb que nem sempre a solucao mais simples em código é a mais optimizada em tempo de execução!

[3] Comentário enviado por jllucca em 23/09/2004 - 10:45h

Ao contrario do ragen não concordo que seu artigo tenha ficado didático. Porque? Pra mim que já sei como funciona a recursividade entendi corretamente, mas para alguem que já sabe programar que não sabe o que é isso fica muito dificil entender apenas dizendo: "Se o o argumento não for menor que dois, a função chama a ela própria com o argumento (x) decrementado de uma unidade e multiplica o valor de retorno por x.".

Conheço pessoas que estão apreendendo a programar que não conseguem entender o "quando" é feito os calculos(no else). Imagino que voce poderia ter explicado de forma mais clara(explicar como é feita a recursividade teoricamente) e, isso, lhe possibilitaria falar de outros assuntos mais interressantes...

[4] Comentário enviado por Czuber em 23/09/2004 - 11:11h

Gostei do artigo quanto à forma como vc sacou as condições e o loop, esta é a parte mais difícil da recursividade. Porém, seria mais didático explicar o algoritmo utilizando um teste de mesa com uma pilha de execução...

Aí vai um exemplo meio tosco: Se for chamada a função fatorial (2)

Pilha de execução:

1-) x = 2; fatorial (2 - 1) - instante inicial

2-)x = 1; fatorial (1); retorna 1 // topo da pilha
x = 2; fatorial (2-1); retorna 2*fatorial(2-1)

3-)x = 2; fatorial (1); retorna 2*1

4-) retorna 2*1 = 2

Espero ter acrescentado!
[]s

[5] Comentário enviado por engos em 23/09/2004 - 14:23h

Concordo com o jllucca, achei que ficou fraca a explicação, sem contar que sem o comentário do Ragen e do Soulripper o artigo ficou muito incompleto.

Bem, você disse: "Em artigos futuros mostrarei outros problemas que são melhores resolvidos usando a recursividade.", espero que nesses artigos você explique porque eles são melhores resolvidos usando a recursividade e explique melhor os seus passos, pois para alguém que já conhece seu artigo não teve nada de novo (ao menos pra mim) e para quem não conhece, sem os comentário continuaria sem conhecer (isso estou supondo)...

Agora, descordo do Czuber, se for para explicar como ele "explicou" nem tenta, pois os que precisam da explicação irião desistir pela complexidade que ficaria compreender (isso já vi acontecer).

Mas no geral achei interessante o artigo e fico na espera pelos artigos futuros.

[]s

[6] Comentário enviado por anao em 23/09/2004 - 20:13h

depois de entender o que é recursividade, basta apenas tomar cuidado com o estouro de pilha (comum caso tente calcular o fatoria de algum numero mais elevado), concordo com o soulrippper, tamanho do codigo nem sempre está associado ao tempo de execucao, pq algumas solucoes iterativas (que nao sao recursivas) em alguns casos é a melhor escolha..
[]s

[7] Comentário enviado por jllucca em 23/09/2004 - 21:05h

Opa,

eu me esqueci de comentar quanto a isso. Realmente, tamanho do codigo não é documento. Afinal um codigo assembler que é em muito maior que outras linguagens é de longue o mais rápido ainda :) . A recursividade como já comentaram é muito pesada para coisas simples. Mas, ela é clara. Na minha opinião tem muitas coisas que fica mais claro num codigo recursivo do que num iterativo. Depois de terem entendido como ele funciona daria pra partir pra tentar fazer um iterativo mais complexo e economico :).

Alguns casos onde recursividade é melhor que utilizar soluções iterativas são em arvores(estrutura de dados parecidade com uma arvore genealogica[seila se é assim q se escreve :p]).

[]'s

[8] Comentário enviado por dedraks em 24/09/2004 - 00:15h

Realmente no caso do fatorial, a solução recursiva não é a mais eficiente. Eu só o escolhi por ser bem simples de entender.
Agora, estruturas como árvores e listas são naturalmente recursivas.
O problema de se mostrar uma estrutura destas é que o artigo ficaria muito complexo e longo, o que o tornaria pouco interessante.

[9] Comentário enviado por jllucca em 24/09/2004 - 11:34h

Não sou de mesma opinião, acredito que se voce souber levar ele de forma correta pode sim ficar interessantissimo! Até, talvez, para iniciantes! Mas, cansativo...

[10] Comentário enviado por sepoys em 25/09/2004 - 23:32h

Gostei do artigo... estou tendo recursividade na universidade, mesmo com todas as explicações do professor, muito alunos não conseguem entender... é um assunto complexos, percebo que mesmo programadores experientes deixam de usar recursividade pela complexidade, e sou da opinão que não vai ser lendo 1 ou 10 artigos sobre recursividade que a pessoa ira aprender, tera sim, que colocar a mão na massa....

[11] Comentário enviado por ron_lima em 24/11/2004 - 09:28h

A recursividade é de fato um recurso poderoso em qualquer linguagem de programação que suporte modularização, não ficando exclusivo à linguagem C. Porém, existe um preço à pagar pela recursividade.

No exemplo dado, a função não recursiva será ligeiramente mais rápida que sua versão recursiva devido a dois efeitos da recursividade: empilhamento e fase ociosa.

O empilhamento ocorre sempre que uma função é ativada. A ativação da função provoca os seguintes efeitos:
- Criação das variáveis locais na pilha (os parâmetros são variáveis locais à função e são alocados na pilha).
- Salvamento da pilha atual, para que seja possível o retorno
- Desvio da execução do programa para a função sendo chamada.

Estas operações são um overhead para uma função recursiva. O outro efeito é a fase ociosa. A função recursiva pode ser dividida em duas fases:
- Fase ativa, que é quando a função executa algum trabalho
- Fase ociosa, ou passiva, que é quando está retornando e desempilhando

Enquanto a fase ativa provoca o empilhamento, a fase passiva provoca o desempilhamento. A função em questão irá ter uma fase ativa do mesmo tamanho da fase ociosa, o que também é um overhead.

Outra desvantagem da função recursiva refere-se ao limite de pilha. A pilha não é uma grandeza ilimitada. Assim sendo, o empilhamento é um recurso que pode ser escasso. O empilhamento exageirado pode levar a um erro do tipo "stack overflow", que é justamente o abuso do uso do empilhamento.

Apesar destas desvantagens, a recursividade é vantajosa para simplificar os algoritmos que têm natureza recursiva. Sempre é possível escrever uma função para resolver o mesmo problema sem recursividade. O que deve ditar a decisão de usar recursividade é:
1. Clareza do código e simplicidade do algoritmo
2. Penalização mínima de performance. Existem situações em que as performance da função recursiva é melhor que a da função não recursiva.

Como eu sempre falo com relação à técnicas de programação e, em especial, com relação à linguagem C: tudo tem seu preço e tudo exige disciplina.

[12] Comentário enviado por danielcc10 em 19/01/2005 - 16:13h

Em primeiro lugar o artigo está errado pois se x < 2 então a função deve retornar 1, ou caso alguém tentando descobrir as deficiências do programa (como eu acabei de fazer apenas olhando o código) perceberá que o algoritmo retorna zero caso a entrada seja zero (e o fatorial de zero é 1).
Em segundo lugar existem realmente muitas formas de se fazer qualquer coisa, e concordo plenamente com o post acima, mas existem casos onde não é possível fugir da recursividade, caso do algoritmo do "QuickSort", então deve-se usar sim mas com cuidado e de preferência sabendo muito bem o que se espera do programa e seus possíveis defeitos.
Uma boa alternativa é a programação dinâmica, que se utiliza da recursividade em primeira instância mas depois passa a fazer apenas cálculos complementares, como por exemplo se guardássemos o valor dos fatoriais encontrados num vetor, assim conforme a necessidade não seria preciso recalcular seu fatorial completamente mas apenas complementar a parte faltante.

[13] Comentário enviado por helsen em 17/05/2005 - 13:58h

Fazendo um teste de mesa no primeiro código do artigo já encontramos uma falha absurda:

int fatorial(int x) {

int i = x;

while ( x > 1 ) {
x = x * (x - 1);
i = i - 1;
}

return x;
}

por exemplo, se x= 4, entao quando acabar o laço while o valor de x=2092 ?

[14] Comentário enviado por diegotosco em 08/11/2005 - 18:20h

No teste do while, a variável a ser testada deveria ser o i, não o x:

while (i > 1)
{
x = x*(x - 1);
i = i - 1;
}

Falô.

[15] Comentário enviado por GeoLinux em 22/02/2007 - 08:05h

O programa que foi referido com exemplo, não retorna o factorial de x. Vou por isso colocar um equivalente, que esse sim dá o factorial.

int factorial(int x) {
int i = x;
if (!x) /* !x é a mesma coisa que x==0 */
return 1;
else
while ( i > 1 ) {
x *= i - 1;
i--;
}
return x;
}

Outro ponto que gostava de focar, era o facto do retorno da função ser muito grande, para os iniciantes existe um novo tipo, que é o long long que veio com a nova norma c99, em que o especificador de conversão é o %lld.

Na forma recursiva, podia-se colocar o problema da seguinte maneira:

int factorial (int x) {
return x == 0 ? 1: x * factorial (x-1);
}

[16] Comentário enviado por foxfilme em 22/04/2007 - 11:46h

ALGUEM PODE ME AJUDAR POR FAVOR preciso fazer um programa que calcule o fatorial de um numero inteiro, nao pode usar recursividade. deve tratar de ocasioe s especiais com fatorial de 0 e de 1.

[17] Comentário enviado por f_Candido em 22/09/2007 - 17:06h

Muito Bom. Parabéns.
Abraços

[18] Comentário enviado por deise_neves em 15/11/2007 - 22:11h

Alguém pode me ajudar em recursividade usando vetores?
Não tenho a minima ideia.
=(
Obrigada!

[19] Comentário enviado por mcr_j em 26/04/2009 - 17:00h

Segue o código do fatorial iterativo :

Fatorial (int x) {
int n;
n= 1;
while(x > 0){
n= n* x;
x = x – 1;
}
return n;
}

De 13 de abril a 23 de maio :
"VII Olimpíada da Computação"
-Equipe ByteCodes
http://www.softwarelivre.org/news/13239
http://forum.locaweb.com.br/showthread.php?p=10001


Contribuir com comentário




Patrocínio

Site hospedado pelo provedor RedeHost.
Linux banner

Destaques

Artigos

Dicas

Tópicos

Top 10 do mês

Scripts