....... Recursividade

25/8/2009

Recursividade
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.

Recursividade
Para se codificar programas de modo recursivo usa-se um procedimento ou sub-rotina, que permite dar um nome a um comando, o qual pode chamar a si próprio. Esta chamada pode ser diretamente recursiva, quando o procedimento P contiver uma referência explícita a si próprio, ou indiretamente recursiva, quando o procedimento P contiver uma referência a outro procedimento Q, que por sua vez contém uma referência direta ou indireta a P.

1

25/8/2009

Recursividade
Exemplo: Soma N primeiros números inteiros Supondo N = 5; S(5) = 1+2+3+4+5 = 15 -> S(5) = S(4) + 5 -> 10 + 5 = 15 S(4) = 1+2+3+4 =10 -> S(4) = S(3) + 4 -> 6 + 4 = 10 S(3) = 1+2+3 =6 -> S(3) = S(2) + 3 -> 3 + 3 = 6 S(2) = 1+2 =3 -> S(2) = S(1) + 2 -> 1 + 2 = 3 S(1) = 1 =1 -> S(1) = 1 --------------->solução trivial

Recursividade
Em se tratando de procedimentos recursivos pode-se 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.

2

25/8/2009

Recursividade
S N 1 S N 1 se N 1 solução trivial N , se N 1 chamada recursiva

main( ) { int n; scanf(“%d”, &n); printf(“%d”, soma(n)); } int soma(int n) { if (n == 1) return (1); else return (n + soma(n – 1)); }

Recursividade main n=4 n=3 soma(4) n=2

1ª)soma

2ª)soma

3ª)soma

4ª)soma

n=1

4+soma(3) 3+soma(2) soma(4)=10 soma(3)=6 2+soma(1)0 soma(2)=3 soma(1)=1

Teste de Mesa para N=4 (somatório dos 4 primeiros números inteiros)