01 - Recursividade - Programação Avançada

Prévia do material em texto

Prof. Raphael Vidal
Raphaelvidal9.webnode.com
Raphael.r.vidal@gmail.com
Programação II
01 - Recursividade
Programas Iterativos x Recursivos?
Programas Iterativos são aqueles que executam uma
sequência de comandos até que uma condição pré-
definida seja encontrada. Essas condições são na forma
de if’s, while’s, repeat’s, case’s ou outras construções da
linguagem de programação
O que é Recursão?
Processo pelo qual uma função chama a si mesma,
repetidamente, um numero finito de vezes.
A recursividade é um dos elementos da programação que
pode causar um certo impacto inicialmente, porém, se
bem utilizado, torna os programas mais simples e
elegantes.
Tipos de Recursão
• Recursão direta: 
Uma função A chama a própria função A. 
• Recursão indireta: 
Uma função A chama uma função B, que por sua vez, 
chama a função A.
Exemplo de Recursão
• Um dos exemplos mais populares de recursividade
direta vem da matemática, com o cálculo do fatorial de
um número. O fatorial de N é definido por:
Recursão
• A seqüência de operações que produz o resultado de 3!
é apresentada a seguir:
Recursão
• Exemplo de execução
Iterativo
#include<stdio.h>
#include<stdlib.h>
int Fatorial(int num)
{
int i, n = 1;
for (i = num; i > 1; i--)
n = n * i;
return n;
}
int main()
{
int num = 3;
printf("O fatorial de %d eh: %d\n", num, Fatorial(num));
system("pause");
}
Recursão
• Algoritmo recursivo para o cálculo do fatorial.
Função Fatorial (int N): int; 
se N = 0 então
Fatorial := 1 
senão
Fatorial := N * Fatorial(N - 1); 
Recursão aqui!
Recursão
• Algoritmo recursivo para o cálculo do fatorial.
#include<stdio.h>
#include <stdlib.h>
int calculaFatorial(int num)
{
if (num <= 1) {
return 1;
} else {
return num * calculaFatorial(num-1);
}
}
int main()
{
int num = 3;
// Imprime o fatorial do número especificado acima
printf("O fatorial de %d eh: %d\n", num, calculaFatorial(num));
system("pause");
}
Recursão aqui!
Recursão
• A pilha na chamada da função Fat(num, 5), tem-se a 
seguinte seqüência de chamadas recursivas: 
Chamada nº Bloco num n ret
0 main 5 - -
1 fat - 5 120
2 fat - 4 24
3 fat - 3 6
4 fat - 2 2
5 fat - 1 1
Quando utilizar?
É bom esclarecer, no entanto, que o emprego de
recursividade nem sempre é uma boa solução, pois
consome muita memória com essas autochamadas da
função.
Diversas implementações ficam muito mais fáceis com a
recursividade. Porém implementações não recursivas
tendem a ser mais eficientes.
Dica para resolução do exercício:
Em todas as funções recursivas existe: 
• Um caso base, ou condição de parada, cujo resultado 
é imediatamente conhecido. 
• Um passo recursivo em que se tenta resolver um 
subproblema do problema inicial. 
Exercício
1. Crie duas funções(uma iterativa e outra recursiva) para 
multiplicar dois números(através da soma sucessiva);
2. Faça um algoritmo recursivo para elevar um número a 
uma potência inteira não negativa.
Exercício
3. Receba um número positivo e mostre como o exemplo:
Digitado: 10
Saída: 10,9,8,7,6,5,4,3,2,1
4. Receba um número positivo e mostre como o exemplo:
Digitado: 10
Saída: 1,2,3,4,5,6,7,8,9,10.
5. Faça um programa que calcule o fatorial do número.