VETORES

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