13
Funções Recursivas by Aquiles Burlamaqui

Funções Recursivas by Aquiles Burlamaqui. Construção de Algoritmos Funções Recursivas Definição Elementos Exemplos Exercícios em Sala T8: Torre de Hanoi

Embed Size (px)

Citation preview

Page 1: Funções Recursivas by Aquiles Burlamaqui. Construção de Algoritmos Funções Recursivas Definição Elementos Exemplos Exercícios em Sala T8: Torre de Hanoi

Funções Recursivasby Aquiles Burlamaqui

Page 2: Funções Recursivas by Aquiles Burlamaqui. Construção de Algoritmos Funções Recursivas Definição Elementos Exemplos Exercícios em Sala T8: Torre de Hanoi

Construção de Algoritmos

Funções Recursivas Definição Elementos Exemplos Exercícios em Sala T8: Torre de Hanoi

Page 3: Funções Recursivas by Aquiles Burlamaqui. Construção de Algoritmos Funções Recursivas Definição Elementos Exemplos Exercícios em Sala T8: Torre de Hanoi

Funções Recursivas

Uma função recursiva é uma função que se refere a si própria. A ideia consiste em utilizar a própria função que estamos a definir na sua definição.

Page 4: Funções Recursivas by Aquiles Burlamaqui. Construção de Algoritmos Funções Recursivas Definição Elementos Exemplos Exercícios em Sala T8: Torre de Hanoi

Funções Recursivas

Em todas as funções recursivas existe: Um passo básico (ou mais) cujo resultado

é imediatamente conhecido. Um passo recursivo em que se tenta

resolver um sub-problema do problema inicial.

Page 5: Funções Recursivas by Aquiles Burlamaqui. Construção de Algoritmos Funções Recursivas Definição Elementos Exemplos Exercícios em Sala T8: Torre de Hanoi

Funções Recursivas

#include <stdio.h> int fatorial( int n ) { int i,p; p = 1; for( i=2; i<=n; i++ ) p = p * i; return p; }

Page 6: Funções Recursivas by Aquiles Burlamaqui. Construção de Algoritmos Funções Recursivas Definição Elementos Exemplos Exercícios em Sala T8: Torre de Hanoi

Funções Recursivas

#include <stdio.h>

int main(){ unsigned int numero; printf("\nEntre com um numero positivo."); scanf("%u", &numero); printf("O fatorial de %u vale %u.", numero, factorial(numero)); getch();}

unsigned int fatorial (unsigned int num){ unsigned int fato; if (num == 1) return (1); else fato = num * fat (num-1); return fato;}

Page 7: Funções Recursivas by Aquiles Burlamaqui. Construção de Algoritmos Funções Recursivas Definição Elementos Exemplos Exercícios em Sala T8: Torre de Hanoi

Funções Recursivas

factorial(6) 6 * factorial(5) 6 * 5 * factorial(4) 6 * 5 * 4 * factorial(3) 6 * 5 * 4 * 3 * factorial(2) 6 * 5 * 4 * 3 * 2 * factorial(1) 6 * 5 * 4 * 3 * 2 * 1 * factorial(0) 6 * 5 * 4 * 3 * 2 * 1 * 1 6 * 5 * 4 * 3 * 2 * 1 6 * 5 * 4 * 3 * 2 6 * 5 * 4 * 6 6 * 5 * 24 6 * 120 720

Page 8: Funções Recursivas by Aquiles Burlamaqui. Construção de Algoritmos Funções Recursivas Definição Elementos Exemplos Exercícios em Sala T8: Torre de Hanoi

Funções Recursivas

Fibonacci fib(1) = 1 fib(2) = 1 fib(n) = fib(n-1) + fib(n-2), para n > 2

Page 9: Funções Recursivas by Aquiles Burlamaqui. Construção de Algoritmos Funções Recursivas Definição Elementos Exemplos Exercícios em Sala T8: Torre de Hanoi

Funções Recursivas

// 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); }

Page 10: Funções Recursivas by Aquiles Burlamaqui. Construção de Algoritmos Funções Recursivas Definição Elementos Exemplos Exercícios em Sala T8: Torre de Hanoi

Funções Recursivas

Recursão versus Iteração Quando usar um ou outro? Recursão

Percurso de uma árvore; Função de Ackermann

Algoritmos de divisão e conquista(Quicksort, etc)

Page 11: Funções Recursivas by Aquiles Burlamaqui. Construção de Algoritmos Funções Recursivas Definição Elementos Exemplos Exercícios em Sala T8: Torre de Hanoi

Funções Recursivas

Linguagens de programação modernas o espaço disponível para o fluxo de controle é geralmente bem menor que o espaço disponível na heap;

Page 12: Funções Recursivas by Aquiles Burlamaqui. Construção de Algoritmos Funções Recursivas Definição Elementos Exemplos Exercícios em Sala T8: Torre de Hanoi

Programa na Memória

Page 13: Funções Recursivas by Aquiles Burlamaqui. Construção de Algoritmos Funções Recursivas Definição Elementos Exemplos Exercícios em Sala T8: Torre de Hanoi

Funções Recursivas

T8: Construir um programa que implemente o jogo Torre de Hanoi( para n discos), permitindo que o usuário tente resolvé-lo como também permita que ele peça a resposta ao computador, e o computador exiba tal resposta visualmente.