Recursividade revisao

Prévia do material em texto

Prof. Sérgio Souza Costa
Recursividade
Recursividade
• Muitas estruturas de dados como listas e árvores são 
recursivas, então é importante compreender 
conceito de recursividade.
* 
▪ A recursividade é uma forma de resolver problemas por meio da divisão 
dos problemas em problemas menores de mesma natureza.
▪ Se a natureza dos subproblemas é a mesma do problema, o mesmo 
método usado para reduzir o problema pode ser usado para reduzir os 
subproblemas e assim por diante.
▪ Quando devemos parar? Quando alcançarmos um caso trivial que 
conhecemos a solução.
* 
Recursividade
Recursividade
• Exemplos de casos triviais:
– Qual o fatorial de 0 ?
– Quanto é um dado X multiplicado por 1 ?
– Quanto é um dado X multiplicado por 0 ?
– Quanto é um dado X elevado a 1 ?
– Quantos elementos tem em uma lista vazia?
▪ Assim, um processo recursivo para a solução de um 
problema consiste em duas partes:
▪ O caso trivial, cuja solução é conhecida;
▪ Um método geral que reduz o problema a um ou mais 
problemas menores (subproblemas) de mesma 
natureza.
▪ Muitas funções podem ser definidas 
recursivamente. Para isso, é preciso identificar as 
duas partes acima.
▪ Exemplo: fatorial de um número e o n-ésimo termo 
da seqüência de Fibonacci.
* 
Recursividade
Função fatorial 
▪ A função fatorial de um inteiro não negativo pode 
ser definida como:
▪ Esta definição estabelece um processo recursivo 
para calcular o fatorial de um inteiro n.
▪ Caso trivial: n=0. 
▪ Método geral: n x (n-1)!.
* 
Função fatorial
▪ Assim, usando-se este processo recursivo, o cálculo 
de 4!, por exemplo, é feito como a seguir:
*
4! =
 
Função fatorial
▪ Assim, usando-se este processo recursivo, o cálculo 
de 4!, por exemplo, é feito como a seguir:
*
4! = 4 * 3!
 
Função fatorial
▪ Assim, usando-se este processo recursivo, o cálculo 
de 4!, por exemplo, é feito como a seguir:
4! = 4 * 3!
 = 4 * (3 * 2!)
Função fatorial
▪ Assim, usando-se este processo recursivo, o cálculo 
de 4!, por exemplo, é feito como a seguir:
4! = 4 * 3!
 = 4 * (3 * 2!)
 = 4 * (3 * (2 * 1!))
Função fatorial
▪ Assim, usando-se este processo recursivo, o cálculo 
de 4!, por exemplo, é feito como a seguir:
4! = 4 * 3!
 = 4 * (3 * 2!)
 = 4 * (3 * (2 * 1!))
 = 4 * (3 * (2 * (1 * 0!)))
Função fatorial
▪ Assim, usando-se este processo recursivo, o cálculo 
de 4!, por exemplo, é feito como a seguir:
4! = 4 * 3!
 = 4 * (3 * 2!)
 = 4 * (3 * (2 * 1!))
 = 4 * (3 * (2 * (1 * 0!)))
 = 4 * (3 * (2 * (1 * 1)))
Função fatorial
▪ Assim, usando-se este processo recursivo, o cálculo 
de 4!, por exemplo, é feito como a seguir:
4! = 4 * 3!
 = 4 * (3 * 2!)
 = 4 * (3 * (2 * 1!))
 = 4 * (3 * (2 * (1 * 0!)))
 = 4 * (3 * (2 * (1 * 1)))
 = 4 * (3 * (2 * 1))
Função fatorial
▪ Assim, usando-se este processo recursivo, o cálculo 
de 4!, por exemplo, é feito como a seguir:
4! = 4 * 3!
 = 4 * (3 * 2!)
 = 4 * (3 * (2 * 1!))
 = 4 * (3 * (2 * (1 * 0!)))
 = 4 * (3 * (2 * (1 * 1)))
 = 4 * (3 * (2 * 1))
 = 4 * (3 * 2)
Função fatorial
▪ Assim, usando-se este processo recursivo, o cálculo 
de 4!, por exemplo, é feito como a seguir:
4! = 4 * 3!
 = 4 * (3 * 2!)
 = 4 * (3 * (2 * 1!))
 = 4 * (3 * (2 * (1 * 0!)))
 = 4 * (3 * (2 * (1 * 1)))
 = 4 * (3 * (2 * 1))
 = 4 * (3 * 2)
 = 4 * 6
Função fatorial
▪ Assim, usando-se este processo recursivo, o cálculo 
de 4!, por exemplo, é feito como a seguir:
*
4! = 4 * 3!
 = 4 * (3 * 2!)
 = 4 * (3 * (2 * 1!))
 = 4 * (3 * (2 * (1 * 0!)))
 = 4 * (3 * (2 * (1 * 1)))
 = 4 * (3 * (2 * 1))
 = 4 * (3 * 2)
 = 4 * 6
 = 24
Mas como uma função recursiva
é de fato implementada no 
computador?
Usando-se o mecanismo conhecido como
Pilha de Execução!
 
Função fatorial
▪ Considere, novamente, o exemplo para 4!:
*
fatorial(4) -> return 4*fatorial(3)
Pilha de Execução
 
Função fatorial
▪ Considere, novamente, o exemplo para 4!:
*
fatorial(4) -> return 4*fatorial(3)
fatorial(3) -> return 3*fatorial(2)
Pilha de Execução
 
Função fatorial
▪ Considere, novamente, o exemplo para 4!:
*
fatorial(4) -> return 4*fatorial(3)
fatorial(3) -> return 3*fatorial(2)
fatorial(2) -> return 2*fatorial(1)
Pilha de Execução
 
Função fatorial
▪ Considere, novamente, o exemplo para 4!:
*
fatorial(4) -> return 4*fatorial(3)
fatorial(3) -> return 3*fatorial(2)
fatorial(2) -> return 2*fatorial(1)
fatorial(1) -> return 1*fatorial(0)
Pilha de Execução
 
Função fatorial
▪ Considere, novamente, o exemplo para 4!:
*
fatorial(4) -> return 4*fatorial(3)
fatorial(3) -> return 3*fatorial(2)
fatorial(2) -> return 2*fatorial(1)
fatorial(1) -> return 1*fatorial(0)
fatorial(0) -> return 1 (caso trivial)
Pilha de Execução
 
Função fatorial
▪ Considere, novamente, o exemplo para 4!:
*
fatorial(4) -> return 4*fatorial(3)
fatorial(3) -> return 3*fatorial(2)
fatorial(2) -> return 2*fatorial(1)
fatorial(1) -> return 1*fatorial(0)
fatorial(0) -> return 1 (caso trivial)
Pilha de Execução
Desempilha fatorial(0)
 
Função fatorial
▪ Considere, novamente, o exemplo para 4!:
*
fatorial(4) -> return 4*fatorial(3)
fatorial(3) -> return 3*fatorial(2)
fatorial(2) -> return 2*fatorial(1)
fatorial(1) -> return 1*1
Desempilha fatorial(1)
 
Função fatorial
▪ Considere, novamente, o exemplo para 4!:
*
fatorial(4) -> return 4*fatorial(3)
fatorial(3) -> return 3*fatorial(2)
fatorial(2) -> return 2*1*1
Desempilha fatorial(2)
 
Função fatorial
▪ Considere, novamente, o exemplo para 4!:
*
fatorial(4) -> return 4*fatorial(3)
fatorial(3) -> return 3*2*1*1
Desempilha fatorial(3)
 
Função fatorial
▪ Considere, novamente, o exemplo para 4!:
*
fatorial(4) -> return 4*3*2*1*1
Desempilha fatorial(4)
 
Função fatorial
▪ Considere, novamente, o exemplo para 4!:
*
Resultado = 24
 
Recursividade
*
"Para fazer um procedimento recursivo é preciso ter fé.”
prof. Siang Wun Song
 
Recursividade
*
"Para fazer um procedimento recursivo é preciso ter fé.”
prof. Siang Wun Song
"Ao tentar resolver o problema, encontrei obstáculos dentro de obstáculos. Por 
isso, adotei uma solução recursiva.” Aluno S.Y., 1998
 
Recursividade
*
"Para fazer um procedimento recursivo é preciso ter fé.”
prof. Siang Wun Song
"Ao tentar resolver o problema, encontrei obstáculos dentro de obstáculos. Por 
isso, adotei uma solução recursiva.” Aluno S.Y., 1998
"To understand recursion, we must first understand recursion.” —anônimo
 
Funções recursivas
• Base do paradigma funcional.
– ○ Lisp, Haskell, Miranda, F#, Scheme, Erland 
– Influenciou diversas: JavaScript, Python,Ruby, Lua 
• Presente em praticamente todas as linguagens, 
mesmo as imperativas, como 
– C, Java, Pascal, ADA ...
* 
Funções recursivas
• Muitos algoritmos complexos são resolvidos através 
de soluções recursivas
– Quick-sort (ordenação rápida)
– Ordenação por intercalação (merge sort)
– Busca binária
• Muitas estruturas de dados são recursivas
– Listas encadeadas
– Árvores binárias, n-árias ...
• Tendem a gerar códigos menores
* 
Recursividade - Natureza
* 
http://upload.wikimedia.org/wikipedia/commons/a/a2/Fibonacci.jpg
http://www.mathsisfun.com/numbers/images/fibonacci-spiral.gif
Recursividade - Natureza
* 
Vamos fazer mais um 
exercício. Na atividade de 
aprofundamento tem mais 
exercícios. Tentem fazer e 
postem suas dúvidas.
Exercício resolvido
• Codifiquem uma função que multiplica um dado 
inteiro “a” por um inteiro “b”, usando somas 
sucessivas. Exemplo:
• 4 * 3 = 3+ 3+ 3 +3 = 12
Exercício resolvido
int mult (int a, int b) {
}
Exercício resolvido
int mult (int a, int b) {
if (a == 0)
return 
}
Exercício resolvido
int mult (int a, int b) {
if (a == 0)
return 0; 
}
Exercício resolvido
int mult (int a, int b) {
if (a == 0)
return 0; 
if (a == 1)
return 
}
Exercício resolvido
int mult (int a, int b) {
if (a == 0)
return 0; 
if (a == 1)
return b;
}Exercício resolvido
int mult (int a, int b) {
if (a == 0)
return 0; 
if (a == 1)
return b;
return b + mult (a-1,b);
}
Vamos testar ?
Vamos testar ?
mult (3,5) 
Vamos testar ?
mult(3,5)=5+mult(2,5)
Vamos testar ?
mult(3,5)=5+mult(2,5)
 =5+5+mult(1,5)
Vamos testar ?
mult(3,5)=5+mult(2,5)
 =5+5+mult(1,5)
 =5+5+5
Vamos testar ?
mult(3,5)=5+mult(2,5)
 =5+5+mult(1,5)
 =5+5+5
 = 15
1. Faça uma função recursiva que calcula a divisão usando subtrações 
sucessivas
int div (int a, int b);
2. Faça uma função recursiva que calcula o resto de uma divisão usando 
subtrações sucessivas.
int mod (int a, int b);
3.Faça uma função recursiva que calcula a potencia de um numero usando 
multiplicações sucessivas.
int pot (int base, int exp);
4. Faça uma função recursiva que calcula a quantidade de caracteres em uma 
string.
int tamanho (char *str)
5. Fazer uma função recursiva que calcule o valor da série S descrita a seguir 
para um valor n > 0 a ser fornecido como parâmetro para a mesma:
S = 1 + 1/2! + 1/3! + ... 1/n!
Exercícios
Tipos Recursivos
Um tipo recursivo é definido em termos de si.
Exemplos de tipos recursivos:
● listas
● árvores
 
A cardinalidade de tipos recursivos é infinita.
 
Os números naturais é outro exemplo de tipos recursivos 
Axiomas de Peano
O matemático Giuseppe Peano (1858-1932) apresentou alguns axiomas sobre números 
naturais, que ficaram posteriormente conhecidos como os Axiomas de Peano. Nele 
precisamos admitir três conceitos primitivos. São eles: zero (denotado por 0), número 
natural e a noção de sucessor de um número natural. Estes axiomas são listados abaixo:
(A1) 0 (zero) e ́ um nu ́mero natural e na ̃o e ́ sucessor de 
um nu ́mero natural2.
(A2) Todo nu ́mero natural tem um u ́nico sucessor, 
que tambe ́m e ́ um nu ́mero natural.
(A3) Se dois nu ́meros naturais tem o mesmo sucessor, 
enta ̃o eles sa ̃o iguais entre si. 
(A4) Se um subconjunto S dos nu ́meros naturais 
possui o elemento zero e tambe ́m o sucessor de todos 
os elementos de S, enta ̃o S e ́ igual ao conjunto dos 
nu ́meros naturais. 
 
 
Tipos Recursivos - Naturais
Exemplos:
0 -> Zero
Tipos Recursivos - Naturais
Exemplos:
0 -> Zero
1 -> Succ (Zero) 
Tipos Recursivos - Naturais
Exemplos:
0 -> Zero
1 -> Succ (Zero) 
2- > Succ ( Succ (Zero))
Tipos Recursivos - Naturais
Exemplos:
0 -> Zero
1 -> Succ (Zero) 
2- > Succ ( Succ (Zero))
3- > Succ ( Succ ( Succ (Zero)))
...
 
typedef struct Nat {
struct Nat* ant;
}* Nat;
Nat Zero () {
return NULL;
}
Nat Succ (Nat a) {
Nat n = malloc (sizeof (Nat));
n->ant = a;
return n;
}
Nat ant (Nat a) {
return a->ant;
}
Numeros Naturais
Definição da estrutura. Observe a 
recursão.
Função que define o Zero
Função que retorna o 
sucessor de um dado a.
Função que retorna o 
antecessor de um dado 
a.
typedef struct Nat {
struct Nat* ant;
}* Nat;
Nat Zero () {
return NULL;
}
Nat Succ (Nat a) {
Nat n = malloc (sizeof (Nat));
n->ant = a;
return n;
}
Nat ant (Nat a) {
return a->ant;
}
Definição da estrutura. Observe a 
recursão.
Função que define o Zero
Função que retorna o 
sucessor de um dado a.
Função que retorna o 
antecessor de um dado 
a.
Em C, ponteiros é o 
recurso que nos 
permite definir tipos 
recursivos
Numeros Naturais
Se b é o número 1, então a + b é definido como sucessor de a. Por 
outro lado, se b fosse 2, a + b seria definido como sucessor de a + 1. 
Ou seja, a + c é o sucessor de a + b, onde b é o antecessor de c. Isso 
pode ser descrito na seguinte função: 
Nat sum (Nat a, Nat c) {
 if (c == Zero () )
return a;
 else {
 return Succ ( sum (a, ant(c)));
}
}
Numeros Naturais
A multiplicação pode ser definida em termos de soma 
sucessivas.
Nat mult (Nat a, Nat b) {
if (a == Zero () )
return Zero ();
else
 return sum (b, (mult (b, ant(a))));
}
Numeros Naturais
A multiplicação pode ser definida em termos de soma 
sucessivas.
Nat mult (Nat a, Nat b) {
if (a == Zero () )
return Zero ();
else
 return sum (b, (mult (b, ant(a))));
}
Numeros Naturais
Baixem e testem o 
código.
https://drive.google.com/file/d/0B_v93GPSzr6FRHFvd1NFUUhxN00/edit?usp=sharing
https://drive.google.com/file/d/0B_v93GPSzr6FRHFvd1NFUUhxN00/edit?usp=sharing
https://drive.google.com/file/d/0B_v93GPSzr6FRHFvd1NFUUhxN00/edit?usp=sharing
https://drive.google.com/file/d/0B_v93GPSzr6FRHFvd1NFUUhxN00/edit?usp=sharing
Atividade
1. Codifiquem a divisão inteira.
2. Codifiquem a função que retorna o resto de uma divisão 
inteira, ou seja, equivalente ao operador %.