Recursividade
• Função recursiva é aquela que chama a si
própria.
• Também pode ser considerado, se chamar
outras funções que, em algum momento,
chamem a primeira função, tornando esse
conjunto de funções um processo recursivo.
• É um recurso de programação que pode ser
usada na linguagem C, Java, Visual Basic, entre
outras.
Recursividade
• As funções recursivas são soluções mais
elegantes e simples, se comparadas a funções
tradicionais, já que executam tarefas repetitivas
sem utilizar nenhuma estrutura de repetição,
como for ou while.
• Essa elegância e simplicidade têm um preço
que requer muita atenção em sua
implementação.
Recursividade
• Uma função pode chamar a si própria por um
número limitado de vezes.
• Esse limite é dado pelo tamanho da pilha. Se o
valor correspondente ao tamanho máximo da pilha
for atingido, haverá um estouro da pilha ou “Stack
Overflow.
• Cada vez que uma função é chamada de forma
recursiva, são alojados e armazenados uma cópia
dos seus parâmetros, de modo a não perder os
valores dos parâmetros das chamadas anteriores.
Funções recursivas contem duas
partes fundamentais:
• Ponto de Parada ou Condição de Parada: é
o ponto onde a função será encerrada.
• Regra Geral: é o método que reduz a
resolução do problema através da invocação
recursiva de casos menores, que por sua vez
são resolvidos pela resolução de casos ainda
menores pela própria função, assim
sucessivamente até atingir o “ponto de parada”
que finaliza a função.
Exemplo de função recursiva:
cálculo do somatório
#include <iostream>
using namespace std;
int soma(int x) {
int y;
if( x == 0 )
{ cout <<x << " ) \n";
return 0;
}
else
{
cout <<" ( "<< x << " + ";
y = x + soma(x -1);
cout <<"soma parcial = "<<y<<"\n";
return y;
}
}
int main() {
int num;
cout << "Digite o numero: ";
cin >> num;;
cout<<"\nA soma de 0 ate "<<num <<" = "<<soma(num)<<"\n";
system("pause");
return 0;
}
Demonstrativo Somatório
5
15
5+Soma(5-1)
5+10
5+(4+Soma(4-1))
5+(4+6)
5+(4+(3+Soma(3-1)))
5+(4+(3+3)
5+(4+(3+(2+Soma(2-1))))
5+(4+(3+(2 +1)))
Exercícios:
1. Fazer uma função recursiva que calcule o fatorial de um número. O
número deverá ser lido no programa principal.
Demonstrativo da solução:
5!
120
5*4!
5*(24)
4*3!
4*(6)
3*2!
3*(2)
2*1!
2*(1)
1
1*(1)
Exercícios:
2. O que fará e qual será o resultado do exercício abaixo?
//Recursividade na Linguagem C
#include <math.h>
#include <iostream>
using namespace std;
int funcao(int x)
{
cout << "\n" << x;
if(abs(x) < 10 )
return 1;
else
return(1 + funcao(x/10));
}
int main()
{
int num;
num=10145;
cout <<" Total: " << funcao(num);
system ("pause");
return 0;
}
Exercícios:
3. Fazer um programa que leia,some 2 valores inteiros e mostre o
resultado da soma. No final do programa, deverá ter uma recursividade
que chame novamente o programa principal, mostre a mensagem
“Digite 1 se desejar executar o programa novamente”,caso positivo,
executar o programa novamente caso negativo, terminar a execução
do programa.
Exercícios:
4. Questão da prova do ENADE 2008.
Os termos da seqüência de Fibonacci são definidos por:
Fibonacci(0) = 0
Fibonacci(1) = 1
Fibonacci(n) = Fibonacci(n-1) + Fibonacci(n-2)
Uma solução recursiva para o cálculo do i-ésimo termo da seqüência é
dada pela função a seguir.
1 funcao fibonacci(inteiro longo n)
2 se((n=0) OU (n=1)) entao
3
retorne n
4 senao
5
retorne fibonacci(n-1) + fibonacci(n-2)
6 fim se
7 fim
Exercícios:
(continuação exercício 4):
Acerca da execução recursiva dessa função, assinale a opção
incorreta.
A) À medida que o valor de n cresce, há um aumento no número de
chamadas recursivas.
B) O método recursivo é o mais eficiente para o cálculo do i-ésimo
termo da seqüência de Fibonacci, pois realiza duas chamadas por
passo da recursão, cada uma mais simples do que a chamada
original.
C) Na linha 5, a ordem de execução é calcular o valor para
fibonacci(n-1) e somente depois calcular o valor para fibonacci(n-2).
D) As condições de parada da recursão são: o valor de n é 0 ou o
valor de n é 1.
• fazer exercício que leia um numero,
calcule em uma função a soma deste
numero de 0 ate o numero lido em uma
função e mostre a soma deste numero.