INF 1007 – Programação II
Aula 05 – Recursividade
Edirlei Soares de Lima
<elima@inf.puc-rio.br>
Introdução
•
As seguintes sentenças são Verdadeiras ou Falsas?
1
2
3
. Alguém diz: “Estou mentido agora!”;
. Alguém diz: “Esta sentença é falsa!”;
. Um homem natural de Creta, em praça pública, anuncia: “Todo
cretense é mentiroso!”;
Introdução
Definições Recursivas
•
•
Em uma definição recursiva um item é definido em termos de
si mesmo, ou seja, o item que está sendo definido aparece
como parte da definição;
Em todas as funções recursivas existe:
–
Caso base (um ou mais) cujo resultado é imediatamente conhecido;
–
Passo recursivo em que se tenta resolver um sub-problema do
problema inicial.
Definições Recursivas
•
•
Função fatorial: ꢀꢁꢂ ꢃ = ꢃ × ꢃ − 1 × … × 1
A função fatorial pode ser definida recursivamente como:
Caso Base
ꢀꢁꢂ ꢃ = ቊ1ꢃ × ꢀꢁꢂ ꢃ − 1 , ꢄꢅ ꢃ > 0
, ꢄꢅ ꢃ = 0
Passo Recursivo
Chamada Recursiva
•
O caso base é uma situação trivial da função, onde calcular o
valor da função é imediato e direto.
Definições Recursivas
•
•
Função fatorial: ꢀꢁꢂ ꢃ = ꢃ × ꢃ − 1 × … × 1
A função fatorial pode ser definida recursivamente como:
Caso Base
ꢀꢁꢂ ꢃ = ቊ1ꢃ × ꢀꢁꢂ ꢃ − 1 , ꢄꢅ ꢃ > 0
, ꢄꢅ ꢃ = 0
Passo Recursivo
Chamada Recursiva
•
O passo recursivo é a aplicação recursiva da função em uma
versão de menor porte do problema.
Definições Recursivas
•
Solução Conceitual:
–
–
–
–
–
Problema de Ordem-n:
ꢁꢂ ꢃ : N → N
A função fat recebe um número
natural n e retorna um número
natural que é o fatorial de n
ꢀ
Precondição:
ꢃ ∈ N
n só pode ser um número natural
Se n é zero, a função fat retorna 1
valor de fat para n-1 é necessário
Caso(s) Base:
ꢃ = 0 → ꢀꢁꢂ ꢃ = 1
Chamada Recursiva:
ꢀ
ꢁꢂ ꢃ − 1
Passo Recursivo:
ꢁꢂ ꢃ = ꢃ ∗ ꢀꢁꢂ ꢃ − 1
A função fat retorna o valor de n
multiplicado pelo valor de fat para
n-1
ꢀ
Funções Recursivas
•
•
Na programação, uma função recursiva é aquela que faz uma
chamada para si mesma;
Essa chamada pode ser:
–
Direta: uma função A chama a ela própria
–
Indireta: função A chama uma função B que, por sua vez, chama A
void func_rec(int n)
{
.
..
func_rec(n-1);
..
Recursao Direta
.
}
Funções Recursivas
•
Função recursiva para cálculo de fatorial:
Caso Base
Passo Recursivo
ꢀ
ꢁꢂ ꢃ = ቊ1
, ꢄꢅ ꢃ = 0
ꢃ × ꢀꢁꢂ ꢃ − 1 , ꢄꢅ ꢃ > 0
Chamada Recursiva
int fat(int n)
{
if (n==0)
Caso Base
return 1;
else
Passo Recursivo
return n * fat(n-1);
}
Funções Recursivas
•
Comportamento de uma função recursiva:
–
Quando uma função é chamada recursivamente, cria-se um ambiente
local para cada chamada;
–
As variáveis locais de chamadas recursivas são independentes entre si,
como se estivéssemos chamando funções diferentes;
Funções Recursivas
include <stdio.h>
#
int fat(int n)
{
int f;
if (n == 0)
f = 1;
else
f = n * fat(n-1);
return f;
}
int main(void)
{
int n = 3, r;
r = fat(n);
printf("Fatorial de %d = %d \n", n, r);
return 0;
}
Funções Recursivas
include <stdio.h>
#
int fat(int n)
{
int f;
if (n == 0)
f = 1;
else
f = n * fat(n-1);
return f;
}
int main(void)
{
int n = 3, r;
r = fat(n);
printf("Fatorial de %d = %d \n", n, r);
return 0;
}
Funções Recursivas
include <stdio.h>
#
int fat(int n)
{
int f;
if (n == 0)
f = 1;
else
f = n * fat(n-1);
return f;
}
int main(void)
{
int n = 3, r;
r = fat(n);
printf("Fatorial de %d = %d \n", n, r);
return 0;
}
Funções Recursivas
include <stdio.h>
#
int fat(int n)
{
int f;
if (n == 0)
f = 1;
else
f = n * fat(n-1);
return f;
}
int main(void)
{
int n = 3, r;
r = fat(n);
printf("Fatorial de %d = %d \n", n, r);
return 0;
}
Funções Recursivas
include <stdio.h>
#
int fat(int n)
{
int f;
if (n == 0)
f = 1;
else
f = n * fat(n-1);
return f;
}
int main(void)
{
int n = 3, r;
r = fat(n);
printf("Fatorial de %d = %d \n", n, r);
return 0;
}
Funções Recursivas
include <stdio.h>
#
int fat(int n)
{
int f;
if (n == 0)
f = 1;
else
f = n * fat(n-1);
return f;
}
int main(void)
{
int n = 3, r;
r = fat(n);
printf("Fatorial de %d = %d \n", n, r);
return 0;
}
Funções Recursivas
include <stdio.h>
#
int fat(int n)
{
int f;
if (n == 0)
f = 1;
else
f = n * fat(n-1);
return f;
}
int main(void)
{
int n = 3, r;
r = fat(n);
printf("Fatorial de %d = %d \n", n, r);
return 0;
}
Funções Recursivas
include <stdio.h>
#
int fat(int n)
{
int f;
if (n == 0)
f = 1;
else
f = n * fat(n-1);
return f;
}
int main(void)
{
int n = 3, r;
r = fat(n);
printf("Fatorial de %d = %d \n", n, r);
return 0;
}
Funções Recursivas
include <stdio.h>
#
int fat(int n)
{
int f;
if (n == 0)
f = 1;
else
f = n * fat(n-1);
return f;
}
int main(void)
{
int n = 3, r;
r = fat(n);
printf("Fatorial de %d = %d \n", n, r);
return 0;
}
Funções Recursivas
•
Exercício: forneça a definição recursiva para a operação
de potenciação:
Caso Base
ꢆꢇ = ቊ1, ꢄꢅ ꢃ = 0
ꢆ × ꢆ(ꢇꢈꢉ), ꢄꢅ ꢃ > 0
Passo Recursivo
int pot(int x, int n)
{
if (n == 0)
return 1;
else
return x * pot(x, n-1);
}
Manipulação de Cadeias de Caracteres
•
É possível utilizar funções recursivas para manipular
cadeias de caracteres;
•
Baseiam-se em uma definição recursiva de cadeias
de caracteres:
–
Uma cadeia de caracteres é:
•
a cadeia de caracteres vazia; ou
•
um caractere seguido de uma cadeia de caracteres.
Manipulação de Cadeias de Caracteres
•
Implementação recursiva da função “imprime”:
void imprime_rec(char* s)
{
if (s[0] != '\0')
{
printf("%c", s[0]);
imprime_rec(&s[1]);
}
}
int main (void)
{
char cidade[] = "Rio de Janeiro";
imprime_rec(&cidade[0]);
return 0;
}
Manipulação de Cadeias de Caracteres
•
Implementação recursiva da função “imprime invertido”?:
void imprime_inv(char* s)
{
if (s[0] != '\0')
{
imprime_inv(&s[1]);
printf("%c", s[0]);
}
}
int main (void)
{
char cidade[] = "Rio de Janeiro";
imprime_inv(&cidade[0]);
return 0;
}
Manipulação de Cadeias de Caracteres
•
Implementação recursiva da função “comprimento”?:
int comprimento(char s[])
{
versão iterativa
int i, n = 0;
for (i=0; s[i] != '\0'; i++)
{
n++;
}
return n;
}
int comprimento_rec(char* s)
{
versão recursiva
if (s[0] == '\0')
return 0;
else
return 1 + comprimento_rec(&s[1]);
}
Leitura Complementar
•
Waldemar Celes, Renato Cerqueira, José Lucas
Rangel, Introdução a Estruturas de Dados, Editora
Campus (2004).
•
Capítulo 4 – Funções