Rodolfo

Disponível somente no TrabalhosFeitos
  • Páginas : 2 (457 palavras )
  • Download(s) : 0
  • Publicado : 22 de novembro de 2012
Ler documento completo
Amostra do texto
Recursividade
Recursividade é a propriedade que uma função tem de chamar a si própria, diretamente ou não. Isto é usado para simplificar um problema. Exemplo mais comum de recursão: função FatorialCaso base 0!=1 1!=1.0!=1 Regra Geral: 2!=2.1!=2.1 n ! = n * (n-1) ! 3!=3.2!=3.2.1 fat(n) = n * fat(n-1) 4!=4.3!=4.3.2.1
1 2

Estrutura de Dados I
Recursão
Conceitos Iniciais

RecursividadeEx: Fatorial de 4 n = 4! = 4 . 3! Caso base 3! = 3 . 2! 2! = 2 . 1! 1! = 1 . 0! 0! = 1 1! = 1 . 1 2! = 2 . 1 3! = 3 . 2 4! = 4 . 6 n = 24
3

Recursividade
Como uma função recursiva pode chamar a simesma indefinidamente, é essencial a existência do caso base, ou condição de parada. No caso do fatorial, o caso base é o zero, cujo valor do fatorial é 1. A partir dele, são encontrados todos osoutros valores.
int fatorial(int n) { if (n = 0) // caso base, onde a recursão return 1; // caso indutivo else return ( n * fatorial( n-1 ) ); }
acaba

4

Como um programa é executado...

Como umprograma é executado...
• Área dinâmica da memória do programa Heap • Memória que foi requisitada dinâmicamente pelo programador (malloc/new)

• Quando um programa é executado, o sistemaoperacional aloca para este uma área na memória do sistema • Internamente, tal segmento de memória é dividido em duas partes: •Pilha

Área da memória alocada

• Área estática da memória do programa•Heap
5

Pilha

• Variáveis globais/locais • Chamada de métodos/funções
6

Chamada de Funções
Quando uma função é chamada, esta é inserida na pilha e executada. Por isso, chamar uma função torna-semais lento do que escrever o código diretamente.
main() { func1(); } func1() { func2(); } main ( ) func1 ( ) func2 ( ) ... }
7

Funções Recursivas
A cada chamada de uma função recursiva, ela éinserida na pilha e novas variáveis são alocadas.
fat(int n) { if (n == 0) return 1; else return n * fat(n-1);
pilha

fat ( 3 ) fat ( 2 ) fat ( 0 ) fat ( 1 ) fat ( 2 ) fat ( 3 )
8

topo da...
tracking img