Recursividade em c++

Universidade de São Paulo – São Carlos Instituto de Ciências Matemáticas e de Computação

Recursão em C

Material preparado pela profa Silvana Maria Affonso de Lara 2º semestre de 2010

ROTEIRO DA AULA
Definição de recursão  Exemplos de recursão  Estrutura da recursão  Vantagens e desvantagens da recursão


2

RECURSÃO EM C

uma função é dita recursiva quando dentro do seu código existe uma chamada para si mesma Ex: cálculo do fatorial de um número: n! = n * (n - 1)!
3

RECURSÃO EM C


A recursão é uma técnica que define um problema em termos de uma ou mais versões menores deste mesmo problema



Esta ferramenta pode ser utilizada sempre que for possível expressar a solução de um problema em função do próprio problema

4

EXEMPLO FATORIAL
#include int fatorial (int n) { if (n == 0) /* condição de parada da recursão */ return 1; else if (n < 0) { printf ("Erro: fatorial de número negativo!\n"); exit(0); } return n*fatorial(n-1);

}

5

EXEMPLO FATORIAL fatorial(5) => (5 ° 0) return 5 • fatorial(4) => (4 ° 0) return 4 • fatorial(3) => (3 ° 0) return 3 • fatorial(2) => (2 ° 0) return 2 • fatorial(1) => (1 ° 0) return 1 • fatorial(0) => (0 == 0) S(2) = S(1) + 2 -> 1 + 2 = 3 S(1) = 1 =1 -> S(1) = 1 --------------->solução trivial

9

RECURSÃO


Em procedimentos recursivos pode ocorrer um problema de terminação do programa, como um “looping interminável ou infinito”.



Portanto, para determinar a terminação das repetições, deve-se:
1) Definir uma função que implica em uma condição de terminação (solução trivial), e 2) Provar que a função decresce a cada passo de repetição, permitindo que, eventualmente, esta solução trivial seja atingida.
10

ESTRUTURA DE UMA RECURSÃO


uma recursão obedece a uma estrutura que deve conter os seguintes elementos:

função (par)



teste de término de recursão utilizando par se teste ok, retorna aqui




processamento aqui a função processa as