Recursividade: entenda os algoritmos recursivos

Algoritmos recursivos são algoritmos que fazem chamadas a si mesmo.

Veja o exemplo desta função que calcula o fatorial de um número:

int fatorial ( int numero ){
          if( numero >0 ) 
                    return( numero * fatorial( numero-1 ) );
                    else return 1;

}

Percebeste a recursividade? A função está chamando a ela mesma!

Bem, suponho que se vc chegou até esta página é porque vc sabe o que é fatorial (se não sabe, então descubra aqui). Agora vamos tentar entender o que um algoritmos recursivo faz, e porque ele chama a si mesmo.

Antes de mais nada, segue abaixo o algoritmo completo em C, que calcula o fatorial de um numero.


#include <stdio.h>
#include <stdlib.h>

int fatorial ( int numero )
{
 if( numero >0 )
 return( numero * fatorial( numero-1 ) );
 else return 1;
}

int main(int argc, char *argv[])
{
 int f, n;

 printf (" Numero: ");
 scanf( "%d", &n );

 f = fatorial ( n );

 printf (" Fatorial: %d\n", f );

system("PAUSE");
 return 0;
}

COMO A RECURSIVIDADE FUNCIONA?

Vamos imaginar que queremos saber o fatorial do numero 3. Quando a função recebe o valor ‘3’, ela faz o seguinte:

numero = if( numero >0 ) return
3 true return( 3 * fatorial( 3-1 ) )

Repare que a função retorna uma chamada a ela mesma, mas agora enviando um valor diferente: 3-1. E a brincadeira continuará enquanto numero for maior que ‘0’:

numero = if( numero >0 ) return
3 true return( 3 * fatorial( 3-1 ) )
3-1 = 2 true return( 2 * fatorial( 2-1 ) )
2-1 = 1 true return( 1* fatorial( 1-1 ) )
1-1 = 0 false 1

Se vc reparou, a cada chamada da função, o programa “enrolava” a gente, deixando a resposta pra depois:

Qual é o fatorial de 3? É 3 * o fatorial de 3-1
Qual é o fatorial de 3-1? É 2 * o fatorial de 2-1
Qual é o fatorial de 2-1? É 1 * o fatorial de 1-1
Qual é o fatorial de 1-1? É um!


O programa só nos deu uma resposta concreta na quarta chamada, quando finalmente ele disse que o fatorial de 1-1 é zero.
E agora, que temos um resultado concreto que a recursividade começa a fazer sentido, pois com uma resposta concreta, podemos responder as outras perguntas (chamadas da função) em aberto:

Qual é o fatorial de 3? É 3 * o fatorial de 3-1
Qual é o fatorial de 3-1? É 2 * o fatorial de 2-1
Qual é o fatorial de 2-1? É 1 * 1 = 1
Qual é o fatorial de 1-1? É um!


“Qual é o fatorial de 2-1?”
“-É 1 vezes o fatorial de 1-1. Ou seja, é 1 * 1. Ou seja, o fatorial de 2-1 é igual a 1.”
E essa já é a resposta para a pergunta do nível de cima:

Qual é o fatorial de 3? É 3 * o fatorial de 3-1
Qual é o fatorial de 3-1? É 2 * 1 = 2
Qual é o fatorial de 2-1? É 1 * 1 = 1
Qual é o fatorial de 1-1? É um!

“Qual é o fatorial de 3-1?”
“-É 2 vezes o fatorial de 1-1. Ou seja, é 2* 1. Ou seja, o fatorial de 3-1 é igual a 2.”
E assim a recursividade vai dando as respostas que estavam incompletas:

Qual é o fatorial de 3? É 3 * 2 = 6
Qual é o fatorial de 3-1? É 2 * 1 = 2
Qual é o fatorial de 2-1? É 1 * 1 = 1
Qual é o fatorial de 1-1? É um!


E assim, chegamos no fim da brincadeira, e descobrimos que o fatorial de 3 é 6. É isso que o algoritmo faz.

Consegue enxergar alguma relação entre essas imagens e a recusividade?

Este slideshow necessita de JavaScript.

Curta Linguagem C no Facebook!

Anúncios

2 ideias sobre “Recursividade: entenda os algoritmos recursivos

  1. José Alcino Furtado

    Eu nunca vi nenhuma aplicação de recursividade além do exemplo do cálculo de fatorial. Ainda é um método complicado de implementar, testar e corrigir. Isso sem falar que, se não usado com moderação pode sobrecarregar a memória.
    Alguém sabe de alguma aplicação prática que fuja desse exemplo?

    Resposta

Deixe um comentário

Preencha os seus dados abaixo ou clique em um ícone para log in:

Logotipo do WordPress.com

Você está comentando utilizando sua conta WordPress.com. Sair / Alterar )

Imagem do Twitter

Você está comentando utilizando sua conta Twitter. Sair / Alterar )

Foto do Facebook

Você está comentando utilizando sua conta Facebook. Sair / Alterar )

Foto do Google+

Você está comentando utilizando sua conta Google+. Sair / Alterar )

Conectando a %s