Aula 11 - Recursividade

Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original

*
Recursividade
*
Se um problema pode ser resolvido facilmente,
resolva o problema;
Se o problema é grande,
elabore uma solução menor do problema,
relacione com o problema maior,
resolva o problema menor,
volte ao problema inicial.
Motivação
*
Definição
Um objeto é dito recursivo se ele consistir parcialmente ou for definido em termos de si mesmo.
Uma função recursiva é uma função que faz uma chamada a si mesma.
	
*
Recursão Direta ou Indireta
Se uma função A contiver uma chamada explícita a si mesma, essa função é dita diretamente recursiva.
A  A
Se uma função A contiver uma chamada a uma função B, que por sua vez contenha uma chamada a função A, a função A é dita indiretamente recursiva.
A  B
B  A
*
Todo problema recursivo deve ter
Um caso base que pode ser resolvido diretamente;
Um passo recursivo que envolve um problema menor.
Caso base interrompe a recursão.
Passos recursivos deve caminhar para caso base.
Recursão
*
Um exemplo
Fatorial de um número. 
1! = 1
2! = 2 * 1
3! = 3 * 2 *1
4! = 4 * 3 * 2 * 1
5! = 5 * 4 * 3 * 2 * 1
5!
*
Função recursiva
Dado um problema:
Subdivide este problema em problemas menores (mais simples) e chama a mesma função para resolvê-lo.
Para de subdividir quando chega em um problema trivial.
*
Voltando ao exemplo
Valor Final = 120
*
Função Fatorial Recursiva
Dado o problema do fatorial de um número:
			n! = n * (n – 1)! para n>1
			1! = 1
			0! = 1
*
Implementando em C
int fatorial(int n)
{
	if(n = = 1 || n == 0)
		return 1;
	else
		return n * fatorial(n-1);
}
*
Chamadas recursivas
fat = fatorial(5);
*
Chamadas recursivas
fat = fatorial(5);
*
Chamadas recursivas
fat = fatorial(5);
*
Chamadas recursivas
fat = fatorial(5);
*
Chamadas recursivas
fat = fatorial(5);
*
Chamadas recursivas
fat = 120
fat = fatorial(5);
*
Exemplo
Escreva uma função que recebe como parâmetro um inteiro positivo n e retorna a soma de todos os números inteiros entre 1 e n.
n = 1 → Soma(1) = 1
n = 2 → Soma(2) = 2 + Soma(1)
n = 3 → Soma(3) = 3 + Soma(2)
…
Genericamente: Soma(n) = n + Soma(n-1)
*
Solução Recursiva:
int Soma (int n) 
{
 if (n == 1)
 {
 return 1;
 } 
 else 
 {
 return n + Soma (n - 1);
 }
}
Exemplo
*
Chamada inicial para a função recursiva :
Exemplo
int main () 
{
 int n;
 printf ("Qual o valor de n? ");
 scanf ("%d", &n);
 printf ("O somatorio de 0 a %d :", n);
 printf ("%d", Soma(n));
}
*
Exemplo
Série de Fibonacci
*
Exemplo
int Fibonacci (int n) 
{
 if (n == 0 || n == 1)
 {
 return n;
 } 
 else 
 {
 return Fibonacci(n-1) + Fibonacci(n-2);
 }
}
*
É melhor não usar recursão:
Quando as chamadas recursivas acontecem apenas no início ou apenas no fim da função
Motivo: cada chamada recursiva reserva memória para as variáveis locais e parâmetros 
Exemplos: as funções somatório e fatorial 
Quando o número de tarefas/cálculos repetidos é muito grande, a execução de um programa pode ficar inviável 
Motivo: em geral, cada chamada recursiva é independente da outra; se duas chamadas recursivas realizam os mesmos cálculos, esses cálculos serão repetidos
Exemplo: a função recursiva para a série de Fibonacci
Recursão
*
Escreva um programa que contenha uma função recursiva que calcule be, em que b e e são números inteiros positivos.
O produto entre dois números inteiros sempre pode ser calculado utilizando-se apenas o operador de adição.
Assim: 2 * 3 = 2 + 2 + 2
Ou seja: x * y = x + x + ...+ x (y vezes)
 Escreva uma função recursiva para o cálculo do produto de dois números, usando apenas o operador de soma.
Escreva um programa que contenha uma função recursiva que receba um número natural n, e devolva a soma dos n primeiros números naturais ímpares.
Exercícios
*