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:

Função inteiro Fatorial (inteiro: n)inteiro: i;Início

result ← 1;para i de 2 até n repita

result ← result * i;Fim paraRetorne(result)

Implementação não Recursiva

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:

Função inteiro Fatorial (inteiro: n)inteiro: i;InícioSe n=0 então

fatorial ← 1;Senão

fatorial ← n*fatorial(n-1)Fim seFim

Implementação Recursiva

RecursãoToda 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

Função inteiro fatorial (inteiro: n)inteiro: i;InícioSe n=0 então

retorne(1)Senão

retorne(n*fatorial(n-1))Fim seFim

Implementação Recursiva

Teste de mesa para n=4

Fatorial = 3 * (Fatorial(2))

Fatorial = 4 * (Fatorial(3))

Fatorial = 2 * (Fatorial(1))

Fatorial = 1 * (Fatorial(0))

Fatorial = 1

1 Fatorial = 1

1 Fatorial = 2

2 Fatorial = 6

6 Fatorial = 24

Sequência de Fibonacci – Definição Iterativa

0 1 1 2 3 5 8 13 …

Simulação:

Anterior = 0 atual = 1 seguinte = 1Anterior = 1 atual = 1 seguinte = 2Anterior = 1 atual = 2 seguinte = 3Anterior = 2 atual = 3 seguinte = 5Anterior = 3 atual = 5 seguinte = 8….

Função inteiro fib(inteiro: fibonacci)Inteiro: i, anterior, atual, seguinteIní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 + anterioranterior ← atualatual ← seguinte

fim parafim se

fim seretorne (atual)

Fim

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ãoO que acontece na memória

Precisamos entender como é feito o controle sobre as variáveis locais em chamadas recursivas.A memória de um sistema computacional é dividida em três partes:Espaço Estático: Contém as variáveis globais e código do programa.Heap: Para alocação dinâmica de memória.Pilha: Para execução de funções.

RecursãoO que acontece na pilha:

Toda vez que uma função é invocada, suas variáveis locais são armazenadas no topo da pilha.Quando uma função termina a sua execução, suas variáveis locais são removidas da pilha. Considere o exemplo:

Função inteiro f1(inteiro: a, inteiro: b)Inteiro: cc←5retorne (c+a+b)Função inteiro f2(inteiro: a, inteiro: b)Inteiro: cc ← f1(b, a)retorne (c)/*Chamada */f2(2, 3)

RecursãoO que acontece na memória

Quando f2(2,3) é invocada, suas variáveis locais são alocadas no topo da pilha.

RecursãoO que acontece na memória

A função f2 invoca a função f1(b,a) e as variáveis locais desta são alocadas no topo da pilha sobre as de f2.

RecursãoO que acontece na memória

A função f1 termina, devolvendo 10. As variáveis locais de f1 são removidas da pilha.

RecursãoO que acontece na memória

Finalmente f2 termina a sua execução devolvendo 10. Suas variáveis locais são removidas da pilha.

RecursãoExemplo 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

Fim

RecursãoExemplo 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)

Início

Se (abs( n )<10) então

retorne (1)

Senão

retorne (1+ digitos(div(n,10))

Fim se

Fim

RecursãoExemplo 6. Escreva uma função recursiva que calcule a soma dos dígitos de um inteiro positivo n. A soma dos dígitos de 132, por exemplo, é 6.

Função inteiro somadigitos(inteiro: n)

Início

Se (n <10) então

retorne (n)

Senão

retorne (mod(n,10)+ somadigitos(div(n,10))

Fim se

Fim

RecursãoExemplo 7. Escreva uma função recursiva que determine o inverso de um número inteiro positivo n, dado o número de dígitos de n. O inverso é obtido pela inversão dos dígitos do número. O inverso do 132, por exemplo, é 231.

Função inteiro inverso(inteiro: n, inteiro: ndig)

Início

Se (n <10) então

retorne (n)

Senão

retorne (mod(n,10)*10**(ndig-1)+ inverso(div(n,10),ndig-1)

Fim se

Fim

RecursãoExemplo 8. Verificar se um número é capicua utilizando uma função recursiva que considere como entrada o número inteiro positivo n e o número de algarismos de n. Um número capicua é aquele número que coincide com seu inverso, de acordo a definição do exemplo 7.

Função lógico capicua(inteiro: n, inteiro: ndig)

Início

Se (n <10) então

retorne (1)

Senão

se (mod(n,10)<>div(n,10**(ndig-1))

retorne (0)

fim se

capicua((div(mod(n,10**(ndig-1))),10),ndig-2)

Fim se

Fim

RecursãoExemplo 9. Seja uma linguagem hipotética na qual não existem operadores para adição, nem subtração. Sabe-se 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

Exemplo 10- 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

Recursão

Busca Sequencial

A C E H L M P R T V

Procurar por R

-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. Se o item for igual ao item que está na metade do vetor, o item foi encontrado

2. Se for menor, procure na primeira metade

3. Se for maior procure na segunda metade

Busca Binária

1 2 3 4 5 6 7 8 9 10

A C E H L M P R T V

Procurar por R

I FX I FX

-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?

Procedimento Busca_Binária(inteiro: x,Inicio, Fim);Inteiro: meioIní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_Bin9aria (x, inicio, fim);

fim sefim se

fim seFim

Busca Binária

Exemplo 11-Problema da Torre de HanóiO 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 sermovimentado 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, cadatransferê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ãoMoveDisco(Orig, Dest)

senãoMoveTorre(n - 1, Orig, Aux, Dest)MoveDisco(Orig, Dest)MoveTorre(n - 1, Aux, Dest, Orig)

fim sefimprocedimento MoveDisco(literal:Orig, Dest)inícioEscreva(“Movimento: ”, Orig, “ -> ”, Dest)fim

Recursão

Uma chamada a MoveTorre(3, ‘A’, ‘C’, ‘B’) teria a seguinte saída:Movimento: A -> CMovimento: A -> BMovimento: C -> BMovimento: A -> CMovimento: B -> AMovimento: B -> CMovimento: A -> C

Recursão

Exemplo 12- A recursividade pode ser utilizada para gerar todas as possíveis permutações de um conjunto de símbolos. Por exemplo, existem seis permutações no conjunto de símbolos A, B e C: ABC, ACB, BAC, BCA, CBA e CAB.

Recursão

O conjunto de permutações de N símbolos é gerado tomando-se cada símbolo por vez e prefixando-o a todas as permutações que resultam dos (N - 1) símbolos restantes. Consequentemente, permutações num conjunto de símbolos podem ser especificadas em termos de permutações num conjunto menor de símbolos. Formule um algoritmo recursivo para este problema.

Solução: O número total de permutações de n objetos é dado por P(n) = n!. Ou seja: para 3 objetos P(3) = 3! = 3 x 2 x 1 = 6 permutações. Para 4 objetos temos: P(4) = 4! = 4 x 3 x 2 x 1 = 24 permutações. O recurso básico para a elaboração do algoritmo consiste em montar uma árvore de recursão para uma “instância” de solução para o problema, por exemplo 3 objetos.

Recursão

procedimento PermutaRecursiva(literal: str[], inteiro: k) inteiro: i,nInicio

n ← tamanho(str) se (k = n) então

escreve (str)senão

para i de k até n repita TroqueCarateres( str, k, i) PermutaRecursiva(str, k + 1)

TroqueCarateres( str, i, k)fim para

fim seFim

/* Chamada */PermutaRecursiva(str,1)

Recursão