Introdução à Programação
Recursão
Tópicos da Aula
Hoje, aprenderemos a usar uma técnica de
programação chamada de recursão
Conceito de Recursão
Definições Recursivas
Casos Base e Geral
Programando Recursivamente
Recursão X Laço
2
Recursão
Uma definição recursiva de um conceito consiste em
utilizar o próprio conceito na definição
Ex: fat(n) = n * fat(n-1)
Definições recursivas em linguagem natural não são,
geralmente, muito úteis
Contudo, em outras situações, uma definição recursiva
pode ser a mais apropriada para explicar um conceito
Recursão é uma técnica de programação que pode
fornecer soluções elegantes para determinados
problemas
Mas, antes, deve-se aprender a pensar
recursivamente!
3
Definições Recursivas: Lista
Considere a seguinte lista de números
24, 88, 40, 37
Podemos definir uma lista de números como:
Uma LISTA é um: número
ou um: número
vírgula
LISTA
Resumindo: uma LISTA é definida ou como um
único número, ou como um número seguido de
uma vírgula seguida de uma LISTA
Utilizamos LISTA para sua própria definição
4
Definições Recursivas: Lista
A parte recursiva da definição de LISTA é
utilizada diversas vezes, até que se possa
utilizar a parte não recursiva
número vírgula
24
,
LISTA
88, 40, 37
88 , 40, 37
Parte não
recursiva da
definição de
LISTA
Parte
recursiva da
definição de
LISTA
40, 37
37
5
Definições Recursivas: Fatorial
Fatorial de um número N (N!), que é inteiro e
positivo, é definido como a multiplicação de
todos os inteiros compreendidos entre 1 e N
(inclusive)
Podemos definir fatorial recursivamente:
0! = 1
N! = N x (N-1)!
Mais uma vez, utilizamos fatorial para sua
própria definição
6
Definições Recursivas: Fatorial
5!
120
5 * 4!
24
4 * 3!
6
3 * 2!
2 * 1!
1 * 0!
1
2
1
7
Caso Base e Caso Geral
Toda definição recursiva deve ter uma parte
recursiva e outra não recursiva
Se não houver a parte não recursiva, o
caminho recursivo nunca termina
Gera uma recursão infinita
Similar a um laço infinito
Denomina-se de caso base, a parte não
recursiva da definição, enquanto o caso geral
é a parte recursiva
8
Definições Recursivas: Fatorial
Fatorial de 4
9
Programação Recursiva
Uma função em C pode chamar ela mesma
Função recursiva
O código de uma função recursiva deve tratar o caso
base e o caso geral
Cada chamada da função cria novos parâmetros e
variáveis locais
Cria-se uma nova instância da função
Como em qualquer chamada de função, assim que a
função termina sua execução, o controle retorna para a
função que a chamou (que neste caso, é outra
instância da mesma função)
Exemplo de Função Recursiva:
Fatorial
int fatorial(int n) {
int resultado;
if (n == 0)
resultado = 1;
Caso Base
else
resultado = n * fatorial(n - 1);
return resultado;
}
Caso Geral
11
Chamando Função Recursiva: Fatorial
int main() {
int fat = fatorial(2);
printf(“Fatorial de 2 é %d”,fat);
return 0;
}
12
Pilha de Execução de Funções
Recursivas
1 – Chamada da função:
cópia do argumento
resultado
n
fat
2
-
resultado
n
resultado
n
<fatorial
fat
<main
4 – Retorno da 3a chamada:
cálculo da expressão
resultado
n
resultado
n
fat
1
1
2
-
2 – Chamada recursiva:
cópia do argumento
<fatorial’
<fatorial
<main
1
2
-
3 – Chamada recursiva:
cálculo da expressão
resultado
n
resultado
n
<fatorial’
resultado
n
<fatorial
fat
<main
5 – Retorno da 2a chamada:
cálculo da expressão
resultado
n
fat
2
2
-
<fatorial
<main
1
0
1
2
-
<fatorial’’
<fatorial’
<fatorial
<main
5 – Retorno da
1a chamada
fat
2
<main
13
Usando Recursividade para resolver
problemas
Problema: Torre de Hanoi
Deve-se transportar todos os discos da primeira estaca até
a última obedecendo as seguintes regras:
1. Só pode ser deslocado um disco por vez (o do topo de uma
estaca)
2. Em nenhum momento um disco maior pode estar sobre um
menor
14
Resolvendo Recursividade o Problema
da Torre de Hanoi
Solução: Torre de Hanoi
1. Mover n – 1 discos da estaca Origem para a Temporária
2. Mover o disco n da estaca Origem para a Destino
3. Mover n – 1 discos da estaca Temporária para a Destino
15
Torre de Hanoi
Caso Base
void mover(int n, char orig, char temp, char dest) {
if (n == 1)
printf("Mova o disco 1 da estaca %c para a estaca
%c\n",orig,dest);
else {
mover (n-1,orig,dest,temp);
printf("Mova o disco %d da estaca %c para a estaca
%c\n",n,orig,dest);
mover(n-1,temp,orig,dest);
}
}
Caso Geral
16
Algoritmo para a Torre de Hanoi com 4
Discos
Início
origem -> destino
17
Algoritmo para a Torre de Hanoi com 4
Discos
origem -> temp
destino -> temp
18
Algoritmo para a Torre de Hanoi com 4
Discos
origem -> destino
temp -> origem
19
Algoritmo para a Torre de Hanoi com 4
Discos
temp -> destino
origem -> destino
20
Pontos Chave de uma Solução
Recursiva
Definir o problema em termos recursivos
Definir o caso geral
Determinar o caso base
Definir uma solução de modo que a cada
chamada recursiva, podemos nos aproximar do
caso base
21
Recursão x Laço
Não é porque existe uma solução recursiva, que
sempre devemos usá-la
Soluções iterativas (com laço) são geralmente mais
eficientes
Soluções recursivas geralmente demandam mais poder de
processamento e memória
Porém, soluções utilizando recursão podem ser mais
elegantes e mais compreensíveis que soluções
iterativas equivalentes
Programador deve analisar caso a caso qual é a melhor
técnica a aplicar para a resolução do problema
22
Resumindo ...
Recursão
Conceito
Exemplos de definições recursivas
Casos Base e Geral
Programando Recursivamente
Recursão X Laço
23
Exercícios
O fatorial ímpar de um numero n ímpar positivo é o produto
de todos os numeros ímpares positivos menores do que ou
iguais a n. Por exemplo, 7! = 1 . 3 . 5 . 7 = 105.
Escreva
funcões
iterativas
e
recursivas
para
a
determinacao do fatorial impar de um inteiro impar dado.
24
Exercícios
/*Funcao iterativa para o calculo do fatorial impar*/
long int FatImpar(int n){
long int Fat;
int i;
if (n % 2 == 1) {
Fat = 1;
for (i = 3; i <= n; i = i + 2)
Fat = Fat * i;
return (Fat);
}
else
return(1);
}
25
Exercícios
/*Funcao recursiva para o calculo do fatorial impar*/
long int FatImparRec(int n) {
if (n % 2 == 1)
if (n == 1)
return(1);
else
return(n*FatImparRec(n-2));
else
return(-1);
}
26
Exercícios
Qual o valor de X (4)?
int X(int n) {
if (n == 1 || n == 2)
return n;
else
return X(n-1) + n * X(n-2);
}
27