Entendendo recursividade com Clojure

Recursividade, em programação, é o uso de uma função que pode se invocar novamente por um número finito de vezes. Utilizamos isso principalmente para não precisar mudar ou depender do estado de algo dentro ou fora de uma função, para que ela continue stateless (não mantenham estado).

A maioria dos loops podem ser re-escritos de maneira recursiva. O grande perigo é tomar um stack overflow por conta da quantidade de chamadas da função, porém, tem como evitar esse problema e eu explico como fazer isso neste artigo.

Neste artigo vamos entender recursividade utilizando a linguagem Clojure como meio para estudo. Eu escolhi a linguagem Clojure para esse exemplo por sua simplicidade e funções utilitárias altamente expressivas.

Recursividade com Clojure

Vamos imaginar um exemplo: a criação de uma função que soma todos os valores dentro de uma estrutura de dados, um vetor.

Sabemos que um vetor possui a seguinte estrutura (na maioria das linguagens):

[0, 1, 2, 3, 4]

Em Clojure é quase a mesma coisa, porém, sem as vírgulas separando os valores de dentro do vetor:

[0 1 2 3 4]

Então precisamos criar uma função que percorra todos os itens, e a cada iteração some o item atual com o próximo item do vetor.

Se pensarmos de maneira estruturada, poderíamos criar um for, como nesse exemplo em Python:

def my_structured_sum (numbers):
    total = 0
    for number in numbers:
        total += number
    return total

E bastaria invocar essa função com:

my_structured_sum([0, 1, 2, 3, 4])

O resultado seria: 10 (0 + 1 + 2 + 3 + 4).

Utilizando recursividade e a linguagem Clojure, podemos criar uma função que soma todos os valores de um vetor com a seguinte estrutura:

(defn my-recursive-sum [total numbers]
    (if (empty? numbers)
        total
        (my-recursive-sum (+ (first numbers) total) (rest numbers))))

E logo em seguida, poderíamos utilizar essa função da seguinte maneira:

(my-recursive-sum 0 [0 1 2 3 4])

O resultado será 10.

Onde defn é a definição de uma função e o nome da função é my-recursive-sum que recebe como argumentos total e numbers, o total é nosso acumulador e numbers será nosso vetor.

Dentro da função, primeiro fazemos uma verificação se o vetor numbers está vazio, pois se estiver, podemos retornar o mesmo, que é o que acontece nessa linha:

(if (empty? numbers)
        total)

Empty? É uma função de Clojure que verifica se um identificador está vazio e, deixando nosso total como parâmetro dessa função logo depois da verificação (empty? numbers), se for verdadeiro, o valor de total será retornado, senão Clojure executa a próxima linha que é a invocação da própria função, mas agora com outros parâmetros.

Na chamada recursiva para my-recursive-sum, recebemos como o argumento para total o valor retornado da avaliação da expressão (+ (first numbers) total), onde somamos (+), o primeiro valor do nosso vetor numbers, (first numbers), com o valor que está em total.

Isso faz com que o valor 0, que foi passado inicialmente para nossa função, seja substituído pelo resultado da avaliação e seja passado novamente para nossa função para que total continue recebendo e acumulando valores.

Mas não é só isso que acontece, também passamos como argumento a expressão (rest numbers) que retorna tudo aquilo que estiver depois do primeiro valor de um vetor. Ou seja, retorna a cauda do vetor.

Então, sempre que temos:

first de [0 1 2 3 4], retorna 0
rest de [0 1 2 3 4], retorna [1 2 3 4]
first de [1 2 3 4], retorna 1
rest de [1 2 3 4], retorna [2 3 4]

O que acontece na chamada da nossa função recursiva é:

(my-recursive-sum 0 [0 1 2 3 4])
(my-recursive-sum 0 [1 2 3 4])
(my-recursive-sum 1 [2 3 4])
(my-recursive-sum 3 [3 4])
(my-recursive-sum 6 [4])
(my-recursive-sum 10 [])

E quando finalmente numbers é passado vazio para nossa função (my-recursive-sum 10 []), caímos na condição (if (empty? numbers)) e total é retornado. Nesse caso, contendo o valor 10.

Mas, o legal seria utilizarmos valores pré definidos com o intuito de entender o conceito de stateless.

Entendendo stateless com recursividade e Clojure

Vamos pegar o mesmo exemplo da função my-recursive-sum e, ao invés de passarmos o vetor diretamente, vamos passar um identificador.

Para criar um identificador, uma “variável”, em Clojure, fazemos:

(def my-vector [0 1 2 3 4])

Agora vamos passar para my-recursive-sum o valor de my-vector.

(my-recursive-sum 0 my-vector)

Receberemos o mesmo retorno, 10, mas será que algo mudou em nosso vetor?

Se invocarmos nosso vetor:

my-vector

Teremos o mesmo valor inicial, [0 1 2 3 4], pois não mexemos em nada do estado da nossa aplicação.

A nossa função é stateless porque ela não altera o valor de nada fora do seu contexto e os valores só existem enquanto ela está executando e processando os dados que foram passados para ela.

Melhorando nossa função recursiva

Imagine utilizarmos a função my-recursive-sum toda hora, sempre passando os valores para os argumentos total e numbers. Não fica um pouco chato e até meio sem sentido ter que passar o valor total como 0 toda vez?

Podemos melhorar a nossa função utilizando um recurso chamado Variadic Functions que utiliza aridade de funções, um conceito matemático, não exclusivo de Clojure, onde o processamento da função varia conforme a quantidade de argumentos passados para ela.

Utilizando variadic functions poderíamos fazer algo como:

(defn hello
    ([] (hello "Eae!?"))
    ([name] (str "Eae, " name "!?")))

Onde: se a função não receber nenhum argumento [], irá retornar “Eae!?”, mas se receber algum argumento [name], então retornará (str “Eae, ” name “!?”), que é uma string, pois a função (str) irá retornar uma string interpolada com name e outra string “!?”.

Isso, dentro de nossa função my-recursive-sum ficaria da seguinte maneira:

(defn my-recursive-sum
    ([numbers] (my-recursive-sum 0 numbers))
    ([total numbers]
        (if (empty? numbers)
            total
            (my-recursive-sum (+ (first numbers) total) (rest numbers)))))

Onde: se recebermos somente um valor, [numbers], que deve ser o vetor, vamos executar my-recursive-sum com 0 e o valor passado como argumento ([numbers] (my-recursive-sum 0 numbers)), se não, vamos executar diretamente a segunda parte da função, que é a chamada com total e numbers, ([total numbers] …) e daí, passamos para nossa recursividade na última linha.

Perceba que, quando recebemos somente o vetor, nós fazemos aquele trabalho de invocar a função passando o valor inicial do nosso acumulador.

Então, agora, poderíamos usar essa função dos seguintes modos:

(my-recursive-sum 0 my-vector)

Ou:

(my-recursive-sum my-vector)

E o resultado seria o mesmo.

Evitando o estouro de pilha em funções recursivas com um recurso de Clojure

Logo no começo do artigo, eu disse que utilizar funções recursivas pode ser perigoso, pois podemos tomar um stack overflow. Podemos estourar a quantidade de memória disponível por conta da quantidade de chamadas de uma mesma função.

Isso acontece porque, a cada chamada da função, os valores não são substituídos ou alterados (lembra do stateless?), mas são criados novos valores em memória. Não alteramos o valor de uma posição de memória, criamos em novas posições.

Em Clojure podemos utilizar uma função chamada recur e essa função tem em seu algoritmo uma otimização chamada Tail Call Optimization (TCO), que não aloca novos espaços de memória a cada chamada, mas reaproveita a última posição.

Para deixar nossas funções recursivas seguras com recur, basta mudarmos a chamada recursiva para:

(defn my-recursive-sum
    ([numbers] (my-recursive-sum 0 numbers))
    ([total numbers]
        (if (empty? numbers)
            total
            (recur (+ (first numbers) total) (rest numbers)))))

Onde na hora em que iríamos invocar my-recursive-sum recursivamente, utilizaremos o recur na última linha do código e o resultado continuará sendo o mesmo, porém, com mais segurança para nosso programa.

Conclusão

Recursividade é muito útil para não modificarmos estados em nossas aplicações e trabalharmos o melhor da programação funcional. Porém, temos que tomar cuidado e sempre procurar otimizar nossas funções com TCO, que em Clojure é possível utilizando a função recur.

Podemos utilizar aridade de funções em Clojure para criar Variadic Functions e “modificar” o comportamento de nossa função dependendo da quantidade de argumentos passados na invocação da mesma.

Clojure é uma linguagem bem legal e recomendo fortemente o estudo da mesma, caso queiramos aprender programação funcional.

Espero que tenha gostado do artigo e, se gostou, comente aqui e compartilhe nas redes sociais.

Referências

De 0 a 10, o quanto você recomendaria este artigo para um amigo?

Powered by: