Lesson12

Recursividade e funções recursivas

Uma solução recursiva para um problema depende da combinação de soluções para instâncias mais pequenas desse mesmo problema. Esta é uma ideia central na computação e na engenharia, e pode ser aplicada a inúmeros problemas. Existe em particular metodologias para resolução de problemas que têm por base soluções recursivas, como dividir para conquistar e programação dinâmica.

Python, tal como a maioria das linguagens de programação, suporta explicitamente soluções recursivas permitindo que as funções possam invocar-se a si mesmas. E, como vimos na última aula, em programação funcional e em linguagens puramente funcionais, estamos limitados ao uso de funções recursivas, não sendo possível o uso de ciclos iterativos.

O poder da recursividade reside na possibilidade de definirmos conjuntos infinitos utilizando expressões finitas. A recursividade pode observar-se ao nível dos cálculos e/ou ao nível da estrutura.

Para além de alguns exemplo que vimos na última aula, também temos utilizado recursividade em muitas definições de sintaxe em BNF. Por exemplo,

<nomes> ::= <nome> | <nome>, <nomes>

Na matemática também utilizamos frequentemente definições recursivas, vejamos o caso do factorial e dos números de Fibonacci, \[\begin{align} n! = & \left\{ \begin{array}{cl} 1 & \text{se } n = 0,\\ n (n-1)! & \text{se } n > 0 \end{array} \right.\\ & \\ fib(n) = & \left\{ \begin{array}{cl} 0 & \text{se } n = 1,\\ 1 & \text{se } n = 2,\\ fib(n-1) + fib(n-2) & \text{se } n > 2 \end{array} \right. \end{align}\]

Em ambos os exemplos observa-se um padrão de repetição, que por vezes pode ser facilmente transformado num ciclo iterativo, mas sendo mais complicado noutros casos. No caso do factorial podemos também utilizar uma expressão "iterativa", \[ n! = \prod_{i=1}^n i \]

Podemos implementar a função factorial seguindo a definição recursiva ou iterativa, respectivamente, como se segue,

def factorial(n):
    if n == 0:
        return 1
    else:
        return n * factorial(n-1)

def factorial(n):
    res = 1
    for i in range(1,n+1):
        res = res * i
    return res

Notar que na implementação recursiva não existem ciclos explícitos, e que o factorial de n é obtido a partir do factorial de um número mais pequeno, neste caso factorial de n-1, i.e., um sub-problema mais pequeno. Para que o algoritmo termine é necessário um caso base, um valor para o qual saibamos o valor do factorial, i.e., um sub-problema base para qual saibamos a solução.

Exercício: Seguir o funcionamento das duas implementações da função factorial em http://pythontutor.com/visualize.html.

Notar também que a versão iterativa dos números de Fibonacci, ainda que exista (de facto até existe uma expressão fechada), não é tão fácil de deduzir.

Em resumo, quer as definições recursivas quer as funções recursivas assentam na existência de:

• de um caso base ou caso terminal, que corresponde à versão mais simples do problema (na realidade, em alguns problemas, podem existir vários casos terminais);
• de um passo recursivo ou caso geral, que corresponde à definição recursiva de uma solução para o problema em termos de soluções para sub-problemas deste mas mais simples.

Vejamos outros exemplos.

Máximo divisor comum

Definição matemática: \[\begin{align} mdc(m, n) = & \left\{ \begin{array}{cl} m & \text{se } n = 0,\\ mdc(n, m\%n) & \text{se } n > 0 \end{array} \right. \end{align}\]

Implementação:

def mdc(m, n)
    if n == 0:
        return m
    else:
        return mdc(n, m%n)

Alisamento de tuplos (tuple flatten)

Definição matemática: \[\begin{align} alisa(t) = & \left\{ \begin{array}{cl} \emptyset & \text{se } t \text{ é vazio},\\ alisa(t_0) \cup alisa(cauda(t)) & \text{se } t_0 \text{ é tuplo}\\ (t_0) \cup alisa(cauda(t)) & \text{se } t_0 \text{ não é tuplo} \end{array} \right. \end{align}\]

Implementação:

def alisa(t):
    if t == ():
        return t
    elif isinstance(t[0], tuple):
        return alisa(t[0]) + alisa(t[1:])
    else:
        return (t[0],) + alisa(t[1:])

Maior subsequência comum (LCS)

Definição matemática em que $|s|=n$ e $|t|=m$: \[\begin{align} lcs(s, t) = & \left\{ \begin{array}{cl} \emptyset & \text{se } s \text{ ou } t \text{ vazio},\\ lcs(s_{1..n-1}, t_{1..m-1}) \cup s_{n} & \text{se } s_n = t_m\\ longest(lcs(s, t_{1..m-1}). lcs(s_{1..n-1}, t)) & \text{se } s_n \neq t_m \end{array} \right. \end{align}\]

Implementação:

def lcs(a, b):
    def longest(a, b):
        if len(a) > len(b):
            return a
        else:
            return b
    
    if len(a) == 0 or len(b) == 0:
        return type(a)()
    elif a[-1] == b[-1]:
        return lcs(a[:-1], b[:-1]) + a[-1:]
    else:
        return longest(lcs(a[:-1], b), lcs(a, b[:-1]))

Exercício: Qual é o problema com esta implementação no que diz respeito à eficiência? Como é que podemos resolver este problema?