Recursividade

Recursividade
DCC119 - Algoritmos

Nesta Aula
Definição de recursão
Uso de recursão
Primeiro Exemplo: Fatorial
Exercícios

2

Definição
Uma função é dita recursiva quando chama a si própria, direta ou indiretamente.
Propósito: expressar sua funcionalidade ou objetivo de maneira mais clara e concisa.
Linguagens que permitem uma função chamar a si própria são ditas recursivas
Linguagens que não permitem são ditas iterativas ou não recursivas
3

Entendendo recursividade

Suponha que alguém no ICE lhe pergunte:
“Como chego à Rua Oswaldo Cruz?”

4

Entendendo recursividade
“Como chego à Rua Oswaldo Cruz?”
Você poderia responder com conjunto completo de direções e referências... mas, se as direções são muito complexas, ou se você não está muito certo de como chegar lá, poderia responder: “Vá até a esquina das ruas Olegário Maciel e Halfeld e então pergunte lá: “Como chego à Rua Oswaldo Cruz?”

5

Entendendo recursividade
“Como chego à Rua Oswaldo Cruz?”
Você poderia responder com conjunto completo de direções e referências... mas, se as direções são muito complexas, ou se você não está muito certo de como chegar lá, poderia responder: “Vá até a esquina das ruas Olegário Maciel e Halfeld e então pergunte lá: “Como chego à Rua Oswaldo Cruz?”

Este é um exemplo de recursão!!!
6

Revendo o problema....
Seu colega queria direções para um destino
Para resolver o problema, você deu um conjunto de instruções indicando como seu colega poderia alcançar seu objetivo
Após chegar ao destino indicado por você, seu colega se depara com nova versão do problema original
Novo problema, idêntico em forma ao original, envolve uma nova localização de partida mais próxima ao destino final!
7

Exemplo de Algoritmo recursivo Cálculo do fatorial de um número n
Aprendemos que n! = n * n-1 * n-2 *

*1

8

Exemplo de Algoritmo recursivo Implementação iterativa muito simples: inteiro Fatorial (inteiro n)
{
inteiro