Aula 12

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

ECT1203 Linguagem de Programação
2012.1
Prof. Diego Rodrigues de Carvalho
Profa. Idalmis Milián Sardina
Prof. Luiz Eduardo Cunha Leite
Prof. Marconi Câmara Rodrigues
Prof. Marcelo Henrique Ramalho Nobre
Aula 12 – Funções Recursivas
Universidade Federal do Rio Grande do Norte
Escola de Ciências e Tecnologia
Hora de silenciar o celular
Manter o celular sempre desligado/silencioso quando estiver em sala de aula
Nunca atender o celular em sala de aula
Revisão da aula passada
Matrizes como argumento de funções
 int calcula(int vet[]);
Passagem de parâmetro é feita por referência
Vetores unidimensionais
Strings: só precisa passar o vetor como parâmetro de entrada (o algoritmo usa o ‘\0’ para descobrir o final da string).
Vetores numéricos: além do vetor precisa ser passado como parâmetro o tamanho dele.
Matrizes bidimensionais: pelo menos o tamanho da coluna precisa ser passado
	int determinante(int matrix[][3]); 
Objetivo da Aula
Responde as seguintes perguntas:
Eu vi que a função main chama uma função, mas essa função que foi chamada pela main pode chamar outra função?
Uma função pode chamar a si mesmo?
Esses são os objetivos da aula
Funções Recursivas
Definição
Elementos
Exemplos
Exercícios em Sala
5
Funções Recursivas
Uma função recursiva é uma função que se refere a si própria. Isto é, uma função é recursiva quando dentro dela está presente uma instrução de chamada a ela própria.
Int funcaoa(int b){
int x;
 x = b-1;
 if(x==0)
 return 1;
 else
 return funcaoa(x);
}
6
Funções Recursivas
7
Alocação de memória
Quando uma função é chamada, memória é alocada para todos os seus parâmetros e variáveis locais.
Toda função ativa tem memória na pilha(com a função atual no topo)
Quando uma função termina a memória é desalocada
Ex:	main() chama f(),
		f() chama g()
		g() chama recursivamente g() 
main()
f()
g()
g()
Funções Recursivas
Em todas as funções recursivas existe:
Uma condição básica (ou mais) cujo resultado é imediatamente conhecido.
	Por exemplo: fatorial(0) = fatorial(1) = 1
Um passo recursivo em que se tenta resolver um sub-problema do problema inicial.
	Por exemplo: fatorial(n) = n * fatorial(n-1)
8
Função Fatorial Recursiva
#include <iostream>
Using namespace std;
int fatorial (int);
int main(){
 int n;
 cout << “Entre com um numero positivo:";
 cin >> n;
 cout <<“Fatorial de “ << n <<“ = ”<< fatorial(n);
	 return 0;
}
int fatorial (int num){
 if (num == 1 || num == 0) return 1;
 else return num * fatorial (num-1);
}
9
Função Fatorial Recursiva
 fatorial(6)
 6 * fatorial(5)
 6 * 5 * fatorial(4)
 6 * 5 * 4 * fatorial(3)
 6 * 5 * 4 * 3 * fatorial(2)
 6 * 5 * 4 * 3 * 2 * fatorial(1)
 6 * 5 * 4 * 3 * 2 * 1
 6 * 5 * 4 * 3 * 2
 6 * 5 * 4 * 6
 6 * 5 * 24
 6 * 120
 720
10
Função Fatorial Iterativa
#include <iostream>
Using namespace std;
int fatorial (int);
int main(){
 int n;
 cout << “Entre com um numero positivo:";
 cin >> n;
 cout <<“Fatorial de “ << n <<“ = ”<< fatorial(n);
	 return 0;
}
int fatorial (int num){
 int fat = 1;
 for (int i=2; i <=num; i++) fat = fat * i;
 return fat;
}
11
Exemplo: série de Fibonnaci
A série de Fibonacci é dada por:
1, 1, 2, 3, 5, 8, 13, 21, ...
12
Exemplo: série de Fibonnaci
// calcula o n-ésimo número de Fibonacci. 
 int fib( int n )
 {
 if( n==1 || n==2 ) 
 return 1;
 else
 return fib(n-1) + fib(n-2);
 }
13
Funções Recursivas
Em geral, a todo procedimento recursivo corresponde um outro não recursivo (iterativo).
Vantagens da recursão:
algoritmos mais concisos;
simplifica a solução de alguns problemas;
facilidade de implementação e compreensão;
algoritmos de divisão e conquista (Quicksort, etc)
Desvantagens:
tendem a ser mais lentos e consumir mais memória
erros de implementação podem levar a estouro de memória.
14
Eliminação de laços
Faça um programa para encontrar o maior elemento de um vetor sem utilizar laço.
O programa deverá ter 3 funções recursivas: 
A primeira será utilizada para o usuário digitar todos os elementos do vetor;
A segunda apresentará na tela todos os elementos armazenados no vetor;
A terceira retornará o maior elemento do vetor armazenado. 
15