Rodolfo

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 Fatorial
Caso 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

Recursividade
Ex: 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 si mesma 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 os outros 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 um programa é 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 sistema operacional 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-se mais 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