Recursividade

Recursividade
DEFINIÇÃO: Um método recursivo é, por definição, aquele método que chama uma instância a mais de si mesmo, com a finalidade de dividir o problema original em partes menores e de mais fácil resolução.
OBSERVAÇÃO:
• Todo método recursivo tem um “if” que resolve se vai chamar recursivamente para diminuir o grau de dificuldade do problema (empilhar chamadas) ou se vai encerrar a recursividade por ter chegado ao nível de solução conhecido pelo algoritmo, garantindo aí a parada (desempilhar chamadas). 1

AED: Recursividade




Definição de novos conceitos: uso de elementos conhecidos.
Mas pensemos no seguinte problema:


Defina o conjunto dos números naturais.

PUC Minas – Curso de Sistemas de Informação

2

AED: Recursividade


Definições recursivas:





Um objeto definido em termos dele próprio
Geralmente, utilizadas para definição de conjuntos infinitos Na programação, são métodos que chamam a sua própria execução

PUC Minas – Curso de Sistemas de Informação

3

AED: Recursividade


Definição recursiva:








1 – Âncora ou caso base: elementos básicos do conjunto, ou ponto de parada do método recursivo
2 – Regra de formação de novos elementos

Exemplo: definição recursiva do fatorial de um número Exercício: definição recursiva da série de
Fibonacci

PUC Minas – Curso de Sistemas de Informação

4

AED: Recursividade


Recursividade na programação


Praticamente basta fazer a tradução da definição formal para a linguagem int fatorial(int n){ if(n==0) return 1; else return n * fatorial (n-1);

}

PUC Minas – Curso de Sistemas de Informação

5

AED: Recursividade


Chamada de uma função


Armazenamento de:
−
−
−
−



Parâmetros
Ponto de retorno
Variáveis locais
Valor de retorno

Registro de ativação

PUC Minas – Curso de Sistemas de Informação

6

AED: Recursividade


Anatomia de uma chamada recursiva:


fatorial(4)
−

−

4 * fatorial(3)

3* fatorial(2)
− 2 * fatorial(1)
− 1 * fatorial (0)
−1
− 1*1 = 1
−2*1=2

3*2=6
4 * 6 = 24