recursividade.tex 4.95 KB
Newer Older
1 2 3 4
\documentclass[apostila.tex]{subfiles}


\begin{document}
Jomaro Rodrigues's avatar
Jomaro Rodrigues committed
5
\chapter{Recursividade}
6

Jomaro Rodrigues's avatar
Jomaro Rodrigues committed
7
Recursividade é uma técnica de programação que envolve utilizar definições recursivas de modo a simplificar vários algoritmos.
8 9

Uma definição recursiva é uma definição que utiliza a si mesma para se definir. A princípio, a ideia
10 11 12 13
pode parecer confusa e obscura, mas na realidade é um conceito relativamente simples.

Por exemplo, é possível definir uma exponenciação dessa maneira:

Jomaro Rodrigues's avatar
Jomaro Rodrigues committed
14
Seja $n, k \in N$,
15

Jomaro Rodrigues's avatar
Jomaro Rodrigues committed
16
$$n^0 = 1$$
17

Jomaro Rodrigues's avatar
Jomaro Rodrigues committed
18
$$n^k = n.n^{k-1}$$
19

Jomaro Rodrigues's avatar
Jomaro Rodrigues committed
20 21
Observe que, no exemplo acima, a exponenciação $n^k$ está sendo definida através de 
uma outra exponenciação $(n^{k-1})$, ou seja, este é um caso em que a exponenciação 
22
é definida através dela mesma (o que é uma definição recursiva ou também chamada de recorrência).
23

Jomaro Rodrigues's avatar
Jomaro Rodrigues committed
24
Analisando um pouco melhor o exemplo acima, $n^{k-1}$ também é uma exponenciação, 
25
portanto poderia utilizar a mesma definição para se definir, ou seja, se tomamos
Jomaro Rodrigues's avatar
Jomaro Rodrigues committed
26
$n^{k-1} = n.n^{k-2}$ e assim podemos definir, $n^{k-3}$, etc.
27

28
Note que deve haver um momento em que a definição termina, pois senão seria 
Jomaro Rodrigues's avatar
Jomaro Rodrigues committed
29 30 31
impossível calcular $n^k$. Por isso, toda definição recursiva deve ser acompanhada
de um caso trivial que será o final da definição. No exemplo apresentado, $n^0 = 1$
é o caso trivial e determina o final da recursividade sobre $n^k$.
32

Jomaro Rodrigues's avatar
Jomaro Rodrigues committed
33
Assim, seria possível calcular, por exemplo $3^3$:
34

Jomaro Rodrigues's avatar
Jomaro Rodrigues committed
35 36 37 38 39 40
\begin{align}
3^3 &= 3.3^2, 
3^2 &= 3.3^1, 
3^1 &= 3.3^0, 
3^0 &= 1 \Rightarrow 3^1 = 3.1, 3^2 = 3.3, 3^3 = 3.3.3
\end{align}
41

42
Na linguagem C, funções podem chamar a si próprias, ou seja, funções podem ser recursivas também,
43 44 45
já que podem ser definidas através delas mesmas.

Para uma linguagem permitir recursividade, uma função deve estar apta a chamar a si própria. Um
46
exemplo clássico de recursividade em programação é a função que calcula o fatorial de um número.
47

Jomaro Rodrigues's avatar
Jomaro Rodrigues committed
48 49
Exemplo 1: Duas versões de fatorial
\begin{lstlisting}
50
// não recursiva 
Jomaro Rodrigues's avatar
Jomaro Rodrigues committed
51
int fat(int n)
52 53 54
{
    int t, resp;
    resp = 1;
Jomaro Rodrigues's avatar
Jomaro Rodrigues committed
55
    
56 57
    for (t = 1; t <= n; t++)
        resp = resp*t;
Jomaro Rodrigues's avatar
Jomaro Rodrigues committed
58
    
59 60
    return resp;
}
61

62
// recursiva 
Jomaro Rodrigues's avatar
Jomaro Rodrigues committed
63
int rfat (int n)
64 65
{
    int resp;
Jomaro Rodrigues's avatar
Jomaro Rodrigues committed
66
    
67
    if (n < 2) return 1;
Jomaro Rodrigues's avatar
Jomaro Rodrigues committed
68 69 70
    
    resp = rfat(n-1)*n;
    
71 72 73 74 75
    return resp;
}
\end{lstlisting}

O funcionamento da função \emph{fat} não recursiva deve estar claro. Ela usa uma repetição começando
76 77 78
com 1 e terminando com o valor objetivado e multiplica progressivamente cada número pelo produto
acumulado.

79 80
A operação da função fat recursiva é um pouco mais complexa. Quando a função \emph{fat} é chamada
com um argumento 1, a função retorna 1 (esse é o caso trivial da definição recursiva do fatorial), caso
Jomaro Rodrigues's avatar
Jomaro Rodrigues committed
81
contrário, ela retorna o produto de $fat(n-1)*n$.
82

83 84
Para avaliar essa expressão, fat é chamada com n-1. Isso acontece até que n seja igual a 1, quando as
chamadas à função começam a retornar. O exemplo abaixo ilustra a configuração da pilha na memória
Jomaro Rodrigues's avatar
Jomaro Rodrigues committed
85
durante cada passo da sequência de execução da função \emph{fat(4)}.
86

87
% FIXME: Inserir a imagem
88

89 90 91
Quando uma função chama a si própria, as novas variáveis locais e os parâmetros são alocados na
pilha (que é uma região da memória) e o código da função é executado com esses novos valores a partir do
início. Uma chamada recursiva não faz uma nova cópia da função. Somente os argumentos e as variáveis
92 93
são novas.

94 95
Quando cada chamada recursiva retorna, as antigas variáveis locais e os parâmetros são removidos da
pilha e a execução recomeça no ponto de chamada da função dentro da função.
96

97 98
A principal vantagem das funções recursivas é que elas podem ser usadas para criar versões mais simples
e de mais fácil compreensão de muitos algoritmos complexos do que os seus equivalentes iterativos.
99 100

Por exemplo, o algoritmo de ordenação rápida é bastante difícil de ser implementado pelo modo
101
iterativo. Além deste, diversos problemas, especialmente os relacionados com IA (inteligência artificial),
102 103
levam a si próprios a soluções recursivas. Finalmente, muitas definições são naturalmente recursivas, o
que torna muito mais fácil implementá-las utilizando recursividade.
104

105 106 107
Na criação de funções recursivas é muito importante que seja definido um caso trivial que determina
quando a função deverá começar a retornar valores. Se não houver um caso que obrigue a função a parar
de chamar a si mesma, o programa certamente irá entrar estourar a pilha, já que a memória não é infinita.
108

109
\section{Exercícios}
110

111
1. Crie uma definição recursiva para as seguintes operações:
112 113

a) soma de dois números a e b;
Jomaro Rodrigues's avatar
Jomaro Rodrigues committed
114

115
b) multiplicação de dois números a e b ;
Jomaro Rodrigues's avatar
Jomaro Rodrigues committed
116

117
c) cálculo do n-ésimo número de uma PA de razão r;
Jomaro Rodrigues's avatar
Jomaro Rodrigues committed
118

119 120
d) cálculo do n-ésimo número de uma PG de razão q;

Jomaro Rodrigues's avatar
Jomaro Rodrigues committed
121
2. Implemente a função soma\_pa (int x, int r, int n) que retorna a soma dos n termos de uma PA de
122 123
termo inicial x e razão r.

Jomaro Rodrigues's avatar
Jomaro Rodrigues committed
124 125 126 127 128
3. Desenhe um diagrama da memória para a seguinte chamada de soma\_pa:
\begin{lstlisting}
int soma_pa(1,3,4):
\end{lstlisting}

129
\end{document}