Algoritmos Computacionais

Artigos sobre lógica de programação por Tiago Madeira

algoritmo: do Lat. algorithmos < Ár. alkharizmi: [Inform.] conjunto de etapas bem definidas necessárias para chegar à resolução de um problema.

Recursão

January 8, 2006

A recursão é uma das técnicas mais simples e úteis que existem para usarmos em nossos algoritmos. Consiste em uma função (denominada recursiva) chamar a si mesmo, até que o retorno seja trivial. Resolvi abordá-la aqui porque alguns algoritmos que estudaremos mais para frente usam funções recursivas.

Em matemática, o número fatorial de LaTeX: n é igual a: $LaTeX: n \times{} n-1 \times{} n-2 \times{} \ldots{} 2 \times{} 1$ .

Logo, por exemplo, LaTeX: 5! (cinco fatorial) seria igual a: $LaTeX: 5 \times{} 4 \times{} 3 \times{} 2 \times{} 1 = 120$ .

Um exemplo bom e simples de recursão é um algoritmo para determinar números fatoriais:

1. função fatorial (n)
2.	se , então
3.		retorna 
4.	senão
5.		retorna 
6.	fim-se
7. fim-função

Domínio de nossa função: $LaTeX: n \in{} \mathbf{N} / n \geq{} 1$ .

Qual o custo desse algoritmo?

Vamos abrir um grande parênteses aqui até a próxima linha horizontal para descobrir qual o custo do nosso algoritmo antes de continuar com a conversa sobre recursão e relembrar/reforçar o post sobre Análise de Algoritmos. Vou colocar o número de vezes que cada instrução é executada, usando o esquema que será o padrão para as próximas vezes que veremos custos:

Número da linha: Número de vezes que é executada..

LaTeX: T(n) = (n) + (n-1) + (1) + (n-1) + (n-1) = 4n - 2

Uma função linear, o tipo de algoritmo mais simples que podemos encontrar, com excessão dos que são uma função constante. Mas o parênteses na verdade não serviu só pra isso. Eu queria aproveitar pra escovar uns bits de nosso código. Você percebeu que o primeiro condicional é executado LaTeX: n-1 vezes, mas só entramos nele uma vez? Então vamos inverter nosso condicional.

1. função fatorial (n)
2.	se , então
3.		retorna 
4.	senão
5.		retorna 
6.	fim-se
7. fim-função

Novo custo

LaTeX: T(n) = (n) + (n-1) + (n-1) + (1) + (1) = 3n

Claro que continua uma função linear, não houve nenhuma grande mudança. Os dois continuam com a mesma ordem de crescimento e tal... LaTeX: 4n+2 comparado com LaTeX: 3n é uma diferença pequena, mas essa solução ficou bem mais elegante. Poxa, diminuímos o custo do algoritmo em $LaTeX: \frac{1}{4}$ ! Hehehe...

Agora, antes de continuar, só vamos definir a notação assintótica desse nosso novo custo!

A fórmula do $LaTeX: \Theta{}$ é: $LaTeX: 0 \leq{} c_{1} g(n) \leq{} f(n) \leq{} c_{2} g(n)$

Substituindo pela nossa função, temos: $LaTeX: c_{1}n \leq{} 3n \leq{} c_{2}n$ . É trivial, que podemos escolher para as duas constantes $LaTeX: c_{1}=c_{2}=3$ e para $LaTeX: n_{0}=0$ . Com isso pretendi mostrar-lhes uma conclusão óbvia que no outro artigo não tinha mostrado para não complicar muito: uma função reta (linear) pertence sempre a notação $LaTeX: \Theta{}(n)$ e uma função quadrática pertence sempre a notação $LaTeX: \Theta{}(n^{2})$ (ora, façam um gráfico das funções e vejam se isso não é óbvio!). Mas vamos aprendendo mais sobre análise de algoritmos com o tempo...

Bom... Continuando com a recursão... Nossa função cria um loop consigo mesma, ao invés de usar um para (for) ou enquanto (while). Ela se repete diminuindo um de LaTeX: n a cada iteração, até que chegue ao valor mínimo LaTeX: 1 aonde a resposta é trivial: .

O que é necessário para criarmos uma recursão? Apenas um ponto de parada! Temos que tomar cuidado para não criarmos loops infinitos cuidando sempre com cada entrada que o usuário pode colocar. Nesse caso, eu determinei que o domínio da função é $LaTeX: n \in{} \mathbf{N} / n \geq{} 1$ . Se o cara colocasse LaTeX: n=0 , minha função iria diminuindo infinitamente... e nunca iria retornar nada!

Para fazer a recursão portanto, precisamos analisar o domínio de nossa função e mais: precisamos conhecer um valor (que vai ser o limite; no caso do fatorial, o valor que sabíamos é que LaTeX: 1! = 1 ).

Acredito que vocês tenham achado tudo simples e que não tenham problema com isso. Funções recursivas vão ser extremamente úteis para nós nos próximos artigos. Vou finalizar mostrando-lhes alguns casos básicos de algoritmos em que podemos usar a recursão:

Números de Fibonacci

1. função fibonacci (n)
2.	se , então
3.		retorna 
4.	senão
5.		retorna 
6.	fim-se
7. fim-função

Domínio de fibonacci(n): $LaTeX: n \in{} N / n \geq{} 1$

Depois descobriremos como calcular os números de Fibonacci mais rápido, mas por enquanto nosso objetivo é a recursão!

Substituir um loop

Vamos supor que você quer imprimir os números de n a 1 e esqueceu a sintaxe do para...

1. função imprime_ate (n)
2.	imprima 
3.	se , então
4.		imprime_ate(n-1)
5.	fim-se
6. fim-função

Domínio de imprime_ate(n): $LaTeX: n \in{} N / n \geq{} 1$

Todo loop pode ser uma recursão e tem alguns que ficam bem mais fáceis se forem! Nesse caso, é claro que seria mais simples usarmos um para!

Outros exemplos

Ordenação por Intercalação (Merge Sort)
Busca em Profundidade (Depth-First Search) em Grafos
Função liveSearchS() em JavaScript do site em que você está agora... Veja você mesmo!
... entre vários outros casos!

Vamos trabalhando com eles com o tempo...

Espero que tenham gostado do artigo (pelo menos, tenho certeza que vocês vão achar mais simples que o último!). Qualquer dúvida, sugestão ou notificação de erro; poste um comentário ou me envie um e-mail.

Compare Preços de: notebooks, acer aspire, hp pavilion, computadores, pentium 4, nintendo wii, ps3, celulares, câmeras digitais

Categoria(s): Básico

3 comentários

#1 | Fernando Sagaz (02/04/2006)

Mto boa explicação ! Estava procurando material sobre recursão e este é bem explicativo.

#2 | Tiago Madeira » Recursão (10/12/2006)

[…] O artigo está em outro local agora: Recursão […]

#3 | Jose Cabicho (11/09/2007)

Gostei d ter gasto alguma da minha atencao neste artigo
saio do artigo satisfeito
gostei imenso dos exemplos
bem gostei

Escreva um comentário

53 assinantes

Mais artigos

Comentários recentes

Matheus Eduardo Maura: Faço engenharia eletrica-eletronica( UNIRP SÃO JOSE DO RIO PRETO), e...
rafael: muito legal o artigo mas teria como resolver esse algoritmo nao consegui de jeito nenhum,...
Roger: Bom artigo. Podia atualizar esse site
Aline Celestrino Bento: o que É ALGORITMO=exemplo:35 :7 porque eu ñ sei ALINE
Claudio: eu gostaria de saber este algoritmo: faça um algoritmo que determine, para um digrafo,...
ingrid morgana gomes paes: que bacana que legau isso e emtesamte e legau para apremder mais a...
Filipe Névola: filipe.bico@hotmail. com
Filipe Névola: Boa noite, gostaria de saber se você tem alguma implementação de menor caminho...
Carlos Luiz Silva Meirelles: estou fazendo curso de informática gratuito patrocindo pelo estado....
Maria Regina de Queiroz: Olá Tiago, li os seus artigos e gostei muito, gostaria se possivel que...

Categorias

Escrevo também...

Tiago Madeira
Site pessoal e blog do autor destes artigos
Mal Vicioso
Blog sobre filosofia e sobre a hipocrisia da sociedade

Sobre o design

Este design foi copiado do CSS Zen Garden e modificado com autorização de seu autor, Gunta Klavina.

Licença

Todo o conteúdo deste site (incluindo textos, imagens, arquivos de áudio e quaisquer outros trabalhos), exceto quando especificado o contrário, está licenciado por Tiago Madeira sob uma Licença Creative Commons.

HTML 4.01 gerado por WordPress em 0.532 segundos.