Recursão
Profa. Graziela Santos de Araújo
[email protected]
www.facom.ufms.br/~gsa
Algoritmos e Programação II, 2010
Motivação
 Conceito fundamental em computação
 Programas elegantes e mais curtos
 Equivalência entre programas recursivos – não-recursivos
 Memória
Recursividade
A definição de recursividade (recursão) aplica-se a funções e
procedimentos. Por isso, vale (re)lembrar os seus conceitos:
 Função: é um módulo que produz um único valor de saída. Ela
pode ser vista como uma expressão que é avaliada para um
único valor, sua saída, assim como uma função em Matemática.
 Procedimento: é um tipo de módulo usado para várias tarefas,
não produzindo valores de saída.
Como a diferença entre função e procedimento é sutil,
utilizaremos os termos funções e procedimentos de forma
indiscriminada durante o curso.
Recursividade
Até agora, foram vistos exemplos de procedimentos chamados
genericamente de iterativos. Recebem este nome pois a
repetição de processos neles inclusos fica explícita, através do
uso de laços.
Um exemplo de procedimento iterativo, para cálculo do
fatorial de um número n, pode ser visto a seguir:
01
Função Fatorial (n)
02
03
04
05
06
07
fat 1
para i 1 até n faça
fat  fat * i
fim para
retorna fat
fim função
Recursividade
 Alguns problemas têm uma estrutura recursiva: cada entrada
do problema contém uma entrada menor do mesmo problema
 Estratégia:
se a entrada do problema é pequena então
resolva-a diretamente;
senão,
reduza-a a uma entrada menor do mesmo problema,
aplique este método à entrada menor
e volte à entrada original.
 Algoritmo recursivo, programa recursivo, função recursiva
 Uma função recursiva é aquela que possui uma ou mais
chamadas a si mesma (chamada recursiva)
Recursividade
 Toda função deve possuir ao menos uma chamada externa a
ela.
 Se todas as chamadas à função são externas, então a função é
dita não-recursiva
 Em geral, a toda função recursiva corresponde uma outra não-
recursiva equivalente
 Correção de um algoritmo recursivo pode ser facilmente
demonstrada usando indução matemática
 A implementação de uma função recursiva pode acarretar
gasto maior de memória, já que durante o processo de
execução da função muitas informações devem ser guardadas
na pilha de execução
Exemplos
 Problema:
Dado um número inteiro n ≥ 0, computar o fatorial n!.
Usamos uma fórmula que nos permite naturalmente
escrever uma função recursiva para calcular n! :
n!
=
1
n x (n-1)!
, se n ≤ 1
, caso contrário
Exemplos – Solução 1
/* Recebe um número inteiro n ≥ 0 e devolve o fatorial de n */
função fat (inteiro n)
inteiro result
se n ≤ 1 então
result  1
senão
result  n * fat(n-1)
retorna result
fim função
Exemplos – Solução 2
/* Recebe um número inteiro n ≥ 0
e devolve o fatorial de n */
função fat (inteiro n)
se n ≤ 1 então
retorna 1
senão
retorna n * fat(n-1)
fim função
fat(3)
fat(2)
fat(1)
devolve 1
devolve 2x1 = 2 x fat(1)
devolve 3x2 = 3 x fat(2)
Exemplos
Os procedimentos recursivos possuem uma descrição mais clara
e concisa, fazendo com que o código do programa que o
implemente seja “enxuto”.
Por outro lado, os programas que implementam procedimentos
recursivos tendem a ser mais custosos (em termos de memória e
tempo) que aqueles que implementam a versão iterativa
correspondente.
 Além disso, a depuração de programas recursivos é um pouco
mais complicada que a de programas iterativos.
Exemplos
 Problema:
Dado um número inteiro n > 0 e uma seqüência de n números
inteiros armazenados em um vetor v, determinar um valor
máximo em v.
Exemplos
/* Recebe um número inteiro n > 0 e um vetor v de números
inteiros com n elementos e devolve um elemento máximo de v */
função maximo(inteiro n, inteiro v[MAX])
inteiro aux
se n = 1 então
retorna v[1]
senão
início
aux  maximo(n-1, v)
se aux > v[n] então
retorna aux
senão
retorna v[n]
fim senão
fim função
Corretude
 Como verificar que uma função recursiva está correta?
Passo 1: escreva o que a função deve fazer;
Passo 2: verifique se a função de fato faz o que deveria fazer
quando a entrada é pequena;
Passo 3: imagine que a entrada é grande e suponha que a
função fará a coisa certa para entradas menores; sob
essa hipótese, verifique que a função faz o que dela se
espera.
Recursividade
 Ao conceito de recursividade está relacionado o conceito
de indução .
 A indução permite determinar a corretude de um
procedimento recursivo.
Recursividade
 A indução é um método de prova matemática que permite a
generalização de uma propriedade a partir de instâncias
particulares onde ela pode ser verificada. A indução pode ser usada
para demonstrar a veracidade de um número infinito de
proposições.
 Seja P(n) uma propriedade que tenha como parâmetro um número
natural n. Para provar que P é válida para todos os valores de n,
devemos provar que:
1. Passo base: P é válida para n = 1;
2. Passo indutivo: Para todo n > 1, se P é válida para n − 1,
então P é válido para n.
Recursividade
Ex: Provar, por indução, a seguinte fórmula:
P(n) = 1+2+3+4+· · ·+n = n(n+1)/2
1. Passo base: Provar que P é valida para n = 1. Fazendo a
substituição do n na fórmula por 1, chegamos a
1 = 1.(1+1)/2
1=1
e está provado.
Recursividade
2. Passo indutivo: Para todo n>1, se P é valida para n – 1, então P
é válido para n.
Suponha que P é válida para n-1. Então podemos afirmar que:
1+2+3+...+(n-1) =
( n  1).n
2
Com base no passo indutivo, vamos provar por que P vale para n.
1+2+3+...+(n-1) + n  (n  1).n  n
2
(n  1).n  2n

2
n ( n  1  2)

2
n( n  1)

.
2
Recursividade
No caso do algoritmo para cálculo do fatorial de um
número, por exemplo, poderíamos provar a sua corretude,
utilizando a prova por indução, da seguinte forma:
1. Passo base: Provar que o algoritmo funciona para n=0.
Como o algoritmo devolve 1 nesse caso, que é exatamente o
valor de 0!, ele funciona para o caso em que n=0;
função fat (inteiro n)
se n ≤ 1 então
retorna 1
senão
retorna n * fat(n-1)
fim função
Recursividade
Cálculo do fatorial de um número
2. Passo indutivo: Para todo n>1, se o algoritmo funciona
para n−1, então ele funciona para n.
Supondo que o algoritmo funciona para n−1, e observando que
o valor de n! corresponde a n × (n − 1)!, ele funciona para n.
Recursividade
Vamos provar a corretude da função maximo utilizando a
prova por indução (na quantidade de elementos n do vetor).
Proposição: A função maximo encontra um maior elemento em
um vetor v com n ≥ 1 números inteiros.
1. Passo base: Se n=1, o maior elemento é o da posição 1.
Recursividade
2. Passo indutivo: Suponha que para qualquer valor inteiro
positivo m < n a função compute corretamente maximo(m, v) .
Suponha agora que temos um vetor v contendo n > 1 números
inteiros.
Chamada externa maximo(n, v) , com n > 1. A função executa:
aux  maximo(n-1, v);
Por hipótese de indução, aux contém um valor máximo para os n−1
primeiros valores do vetor v. Então, a função decide quem é maior:
aux ou v[n] .