Algoritmos e Estruturas de Dados I –
Recursão
Profa. Mercedes Gonzales
Márquez
Recursão

A solução de um problema é dita recursiva quando
ela é escrita em função de si própria para instancias
menores do problema. Veja, por exemplo, o
problema de calcular o fatorial de um número n. A
solução iterativa pode ser facilmente implementado
assim:
Implementação não Recursiva
Função inteiro Fatorial (inteiro: n)
inteiro: i;
Início
result ← 1;
para i de 2 até n repita
result ← result * i;
Fim para
Retorne(result)
Recursão

A solução recursiva está diretamente ligada ao
conceito de indução matemática, no qual usa-se
como hipótese que a solução de um problema de
tamanho n pode ser obtida a partir da sua solução
de tamanho menor, por exemplo, n-1. No caso do
exemplo do fatorial teriamos:
Implementação Recursiva
Função inteiro Fatorial (inteiro: n)
inteiro: i;
Início
Se n=0 então
fatorial ← 1;
Senão
fatorial ← n*fatorial(n-1)
Fim se
Fim
Recursão
Toda recursão é composta por:
● Caso base
– Uma ou mais instâncias do problema que podem ser
solucionadas facilmente (solução trivial)
 Chamadas Recursivas
– O objeto define-se em termos de si próprio,
procurando convergir para o caso base.
Por exemplo, o fatorial de um número n pode ser
calculado a partir do fatorial do número n−1.
Recursão

Esquematicamente, os algoritmos recursivos tem a
seguinte forma:
Se <condição para o caso base> então
resolução direta para o caso base
Senão
uma ou mais chamadas recursivas
Fim se

Sem a condição de parada, expressa no caso base,
uma recursão iria se repetir indefinidamente.
Recursão
Implementação Recursiva
Função inteiro fatorial (inteiro: n)
inteiro: i;
Início
Se n=0 então
retorne(1)
Senão
retorne(n*fatorial(n-1))
Fim se
Fim
Teste de mesa para n=4
Fatorial = 1
Fatorial = 1 * (Fatorial(0))
1
Fatorial = 1
Fatorial = 2 * (Fatorial(1))
1
Fatorial = 2
Fatorial = 3 * (Fatorial(2))
2
Fatorial = 6
6
Fatorial = 4 * (Fatorial(3))
Fatorial = 24
Sequência de Fibonacci – Definição
Iterativa
0 1 1 2 3 5 8 13 …
Simulação:
Anterior = 0
Anterior = 1
Anterior = 1
Anterior = 2
Anterior = 3
….
atual = 1
atual = 1
atual = 2
atual = 3
atual = 5
seguinte = 1
seguinte = 2
seguinte = 3
seguinte = 5
seguinte = 8
Função inteiro fib(inteiro: fibonacci)
Inteiro: i, anterior, atual, seguinte
Início
se (fibonacci = 1)
retorne (0)
senão se (fibonacci = 2)
retorne (1)
senão
anterior ← 0
atual ← 1
para i de 3 até fibonacci repita
seguinte ← atual + anterior
anterior ← atual
atual ← seguinte
fim para
fim se
fim se
retorne (atual)
Sequência de Fibonacci – Definição
Recursiva
fib(1) = 0
fib(2) = 1
fib(3) = fib(2) + fib(1)
fib(4) = fib(3) + fib(2)
Fib(n) = fib(n-1) + fib(n - 2)
Função inteiro fib_rec(inteiro: n)
inteiro: anterior, atual, seguinte
Início
se (fibonacci = 1)
retorne (0)
senão se (fibonacci = 2)
retorne (1)
senão
retorne fib_rec(fibonacci - 1) + fib_rec(fibonacci - 2)
fim se
fim se
Fim
Recursão
Exemplo 3. Soma de elementos de um vetor : Faça um
algoritmo que preencha por leitura um vetor de 10
elementos inteiros, imprima o seu conteúdo, e o
resultado do somatório dos seus elementos, calculado
por uma função recursiva.
Função inteiro soma(inteiro: n)
Início
se (n = 1)
retorne (v[n])
senão
retorne (v[n]+soma(n-1))
Fim
Recursão
Exemplo 4. Escreva uma função recursiva que recebe
como parâmetros um número real X e um inteiro n e
retorna o valor de Xn.
Obs.:n pode ser negativo.
Função Real Potencia(real: X,inteiro: n)
Início
Se ( n ==0 ) então retorne (1)
Senão
se ( n <0 ) então
retorne (1 / (X* Potencia(X, abs(N)-1))
senão retorne (X* Potencia(X, N -1))
Fim se
Fim se
Recursão
Exemplo
5. Reescreva a função abaixo tornando-a
recursiva. Esta função conta o número de algarismos
(dígitos) que possui um número inteiro n.
Função inteiro digitos(inteiro: n)
Inteiro: cont
Início
cont ← 1;
enquanto (abs(n )>9) faça
n = div(n,10)
cont ← cont+1
Fim enquanto
retorne (cont)
Fim
Recursão
Função inteiro digitos(inteiro: n)
Inteiro: cont
Início
Se (abs( n )<10) então
retorne (1)
Senão
retorne (1+ digitos(div(n,10))
Fim se
Fim
Recursão
Exemplo
6. Seja uma linguagem hipotética na qual não
existem operadores para adição, nem subtração. Sabese que nesta linguagem, existe uma função prox(n) que
dá o sucessor do número n, e existe também uma função
ant(n) que dá o predecessor de um número n. Usando
apenas essas funções (prox e ant), defina a função
recursiva som(x,y), que toma como argumento os
números naturais x e y, e retorna sua soma.
Recursão
Função inteiro som(inteiro: x,y)
Início
Se (x=0) então
retorne (y)
Senão
se (y=0) então
retorne (x)
senão
retorne (som(ant(x),prox(y))
Fim se
Fim
Recursão
Exemplo 7- Faça um algoritmo que realize uma busca em
um vetor ordenado de elementos.

Pode-se realizar a busca de duas formas:
–
–
Busca Sequencial: os elementos são pesquisados
fazendo a varredura completa do vetor (ineficiente). O
pior caso ocorrerá quando o elemento estiver no último
índice do vetor.
Busca Binária
Busca Sequencial
Procurar por R
A
C
E
H
L
M
P
R
T
V
-8 Comparações!
-Se estivermos procurando o item V, o número de comparações seria
a quantidade de elementos no vetor
-O ideal seria dividir o vetor pela metade para então procurar (Busca
Binária)
Busca Binária


Divide seu vetor em duas metades
Três condições
1.
2.
3.
Se o item for igual ao item que está na metade do
vetor, o item foi encontrado
Se for menor, procure na primeira metade
Se for maior procure na segunda metade
Busca Binária
Procurar por P
1
2
3
4
5
6
7
8
9
10
A
C
E
H
L
M
P
R
T
V
X
I
I
X
F
-2 Comparações!
-Casos piores: quando os itens estiverem no início do vetor. Nesse
caso, seria melhor utilizar busca seqüencial. Mas como saber quando
o ítem está no início do vetor?
Busca Binária
Procedimento Busca_Binária(inteiro: x,Inicio, Fim);
Inteiro: meio
Início
meio ← div((inicio + fim), 2)
Se fim < inicio então
escreva (‘Elemento Não Encontrado’)
Senão se (v[meio]) = x então
escreva (‘Elemento está na posição ’,meio)
senão
se v[meio] < x então
inicio ← meio +1;
Busca_Binaria (x, inicio, fim);
senão
fim ← meio - 1;
Busca_Binaria (x, inicio, fim);
fim se
fim se
fim se
Recursão
Exemplo 8-Problema da Torre de Hanói
O problema ou quebra-cabeça conhecido como torre de
Hanói consiste em transferir, com o menor número de
movimentos, a torre composta por N discos do pino A
(origem) para o pino C (destino), utilizando o pino B como
auxiliar. Somente um disco pode ser
movimentado de cada vez e um disco não pode ser
colocado sobre outro disco de menor diâmetro.
Recursão
Solução: Transferir a torre com N-1 discos de A para B, mover
o maior disco de A para C e transferir a torre com N-1 de B
para C. Embora não seja possível transferir a torre com N-1 de
uma só vez, o problema torna-se mais simples: mover um disco
e transferir duas torres com N-2 discos. Assim, cada
transferência de torre implica em mover um disco e transferir
de duas torres com um disco a menos e isso deve ser feito até
que torre consista de um único disco.
Recursão
procedimento MoveTorre(inteiro:n, literal: Orig, Dest, Aux)
início
se n = 1 então
MoveDisco(Orig, Dest)
senão
MoveTorre(n - 1, Orig, Aux, Dest)
MoveDisco(Orig, Dest)
MoveTorre(n - 1, Aux, Dest, Orig)
fim se
fim
procedimento MoveDisco(literal:Orig, Dest)
início
Escreva(“Movimento: ”, Orig, “ -> ”, Dest)
fim
Recursão
Uma chamada a MoveTorre(3, ‘A’, ‘C’, ‘B’) teria a seguinte
saída:
Movimento: A -> C
Movimento: A -> B
Movimento: C -> B
Movimento: A -> C
Movimento: B -> A
Movimento: B -> C
Movimento: A -> C