Profa. Graziela Santos de Araújogsa@facom.ufms.br

www.facom.ufms.br/~gsaAlgoritmos e Programação II,

2010

Recursão

Motivação

Conceito fundamental em computaçãoProgramas elegantes e mais curtosEquivalência entre programas recursivos –

não-recursivosMemória

RecursividadeA 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.

RecursividadeAté 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 fat 1

03 para i 1 até n faça

04 fat fat * i

05 fim para

06 retorna fat

07 fim função

RecursividadeAlguns 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 menore 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)

RecursividadeToda 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

ExemplosProblema: Problema:

Usamos uma fórmula que nos permite naturalmente escrever uma função recursiva para calcular n! :

Dado um número inteiro n ≥ 0, computar o fatorial n!.

n! = 1 , se n ≤ 1

n x (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ãoresult 1

senãoresult n * fat(n-1)

retorna resultfim função

Exemplos – Solução 2fat(3)

fat(2)

fat(1)

devolve 1

devolve 2x1 = 2 x fat(1)

devolve 3x2 = 3 x fat(2)

/* Recebe um número inteiro n ≥ 0 e devolve o fatorial de n */

função fat (inteiro n)

se n ≤ 1 entãoretorna 1

senãoretorna n * fat(n-1)

fim função

ExemplosOs 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: 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

CorretudeComo 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.

RecursividadeA 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.

RecursividadeEx: 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)/21 = 1

e está provado.

Recursividade2. Passo indutivo: Para todo n>1, se P é valida

para n – 1, então P é válido para n.

Com base no passo indutivo, vamos provar por que P vale para n.1+2+3+...+(n-1) + n

Suponha que P é válida para n-1. Então podemos afirmar que:

1+2+3+...+(n-1) = 2).1( nn

nnn

2

).1(

2

)21(2

2).1(

nn

nnn

.2

)1(

nn

RecursividadeNo 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 1senão

retorna n * fat(n-1)fim função

RecursividadeCá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.

RecursividadeVamos 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.

Recursividade2. 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úmerosinteiros.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] .