Artigo original: Recursion is not hard: a step-by-step walkthrough of this useful programming technique

Escrito por: Kevin Turney

Já vou dizendo isso de cara: você sabe os eventos que acontecem quando uma função é invocada? Não? Então, começaremos daqui.

Chamando uma função

Quando nós chamamos uma função, um contexto de execução ocorre na pilha de execução. Vamos entrar em detalhes mais específicos abaixo.

Primeiro, o que é uma pilha?

Uma pilha é uma estrutura de dados que opera com base em "o último a entrar é o primeiro a sair". Um item é "colocado" (em inglês, pushed) em uma pilha quando o estamos adicionando e é "retirado" (em inglês, popped) da pilha quando queremos removê-lo.

Usar uma pilha é um método de ordenar um determinado número de operações para a execução.

Agora, o que seria um contexto de execução? Um contexto de execução é criado quando temos uma chamada de função. Esse contexto ocorre em uma pilha de execução, uma ordem de operações. O item que é sempre o primeiro nessa pilha é o contexto de execução global. Logo após, estão os contextos criados pelas funções.

Esses contextos de execução tem propriedades, um objeto de ativação e um "this" vinculado. O "this" vinculado é uma referência de volta ao contexto de execução. O objeto de ativação inclui: parâmetros passados, declaração de variáveis e declaração de funções.

Então, toda vez que colocamos um novo contexto na pilha, normalmente, temos tudo de que precisamos para executar o código.

Por que eu disse normalmente?

Com recursão, estamos esperando retornar valores vindo de outros contextos de execução. Esses outros contextos de execução estão em pontos mais altos na pilha. Quando o último item na pilha finaliza a execução, esse contexto gerado retorna um valor. Esse valor retornado é passado como um valor retornado pelo caso recursivo para o próximo item. O contexto de execução, então, é retirado da pilha.

Recursão

Então, o que é recursão?

Uma função recursiva é uma função que chama a si mesma até que a "condição base" seja verdadeira e a execução pare.

Enquanto for falsa, continuaremos colocando o contexto de execução em cima da pilha. Isso pode acontecer até que tenhamos um sobrefluxo da pilha – ou, em inglês, "stack overflow". Um stack overflow ocorre quando ficamos sem memória para manter os itens na pilha.

yEbQk71bUba6KLDWGXuamXQlntQU4mkFaoO4

Em geral, uma função recursiva tem ao menos duas partes: uma condição base e, ao menos, um caso recursivo.

Vamos olhar um exemplo clássico.

Fatorial

const fatorial = function(num) {
	debugger;
    if (num === 0 || num === 1) {
    	return 1  
    } else {
    	return num * fatorial(num - 1)
    }
}
fatorial(5)

Aqui, estamos tentando encontrar 5! (o fatorial de cinco). A função fatorial (texto em inglês) é definida como o produto de todos os números positivos menores ou iguais ao seu argumento.

A primeira condição é: "se o parâmetro passado for igual a 0 ou 1, terminaremos a chamada e retornaremos 1".

Para os casos recursivos, faremos o seguinte:

"Se o parâmetro não for 0 ou 1, passaremos o valor de num vezes o valor de retorno da função chamada outra vez com o argumento de num-1".

Então, se chamarmos fatorial(0), a função retornará 1 e nunca atingirá o caso recursivo.

A mesma situação ocorre com fatorial(1).

Podemos ver o que está acontecendo se inserirmos uma instrução debugger dentro do código e se usarmos as ferramentas do desenvolvedor para segui-lo e observar a chamada da pilha (em inglês, stack).

  1. A stack de execução coloca o 5 como argumento dentro da função fatorial(). O caso base é falso, entrando na condição recursiva.
  2. A stack de execução então chama a função fatorial() uma segunda vez com o argumento num-1 (4) como argumento. O caso base é falso entrando, assim, na condição recursiva.
  3. A stack de execução chamará fatorial() uma terceira vez com o argumento num-1 (3). O caso base é falso. Portanto, outra vez, entramos na condição recursiva.
  4. A stack de execução chama fatorial() uma quarta vez com num-1 (2) como seu argumento. O caso base é falso. Entramos na condição recursiva.
  5. A stack executa fatorial() uma quinta vez com  num-1 (1) como seu argumento. Aqui o caso base é verdadeiro. Então, retornamos 1.

Nesse ponto, diminuímos o argumento passado por 1 em cada chamada de função, até alcançarmos a condição de retorno 1.

6. A partir daí, o último contexto de execução completa num === 1. Então, a função retorna 1.

7. A seguir, temos num === 2. O valor retornado é 2. (1×2).

8. Depois, temos num === 3. Retornamos 6. (2×3). Até agora, temos 1×2×3.

9. Posteriormente, temos num === 4, (4×6). 24 é o valor retornado no próximo contexto.

10. Finalmente, num === 5, (5×24) e, aqui, teremos 120 como valor final.

KioR-yl8aB2lxriDCulsNMTivQ1J5xlmEyrg

Recursão é bem elegante, certo?

Poderíamos ter feito a mesma coisa com um laço for ou while, mas, usando recursão, temos uma alternativa mais apresentável e bonita.

É por isso que usamos soluções recursivas.

Muitas vezes, um problema dissecado em partes menores é mais eficiente e ajuda a superá-lo mais facilmente. Desse modo, recursão é uma abordagem do tipo dividir-e-conquistar para resolver obstáculos.

  • Subproblemas são mais fáceis de solucionar que o problema original;
  • Soluções para subproblemas são combinadas para resolver o problema original.

"Dividir-e-conquistar" é bastante utilizado para atravessar ou buscar em estrutura de dados como em árvores de busca binária, gráficos e pilhas. Isso também funciona com muitos algoritmos de ordenação, como quicksort e heapsort (links em inglês).

Vamos trabalhar com alguns exemplos. Usaremos as ferramentas do desenvolvedor para ter um entendimento conceitual do que está acontecendo, onde e quando. Vamos lembrar de usar a ferramenta debugger e seguir passo a passo cada parte do processo.

Fibonacci

const fibonacci = function(num) {
    if (num <= 1) {
    	return num
    } else {
        return fibonacci(num - 1) + fibonacci(num - 2)
	}
}

fibonacci(5);

Arrays recursivos

function aplainar(arr) {
	var result = []  arr.forEach(function(element) {
    	if (!Array.isArray(element)) {
        	result.push(element)
        } else {
        	result = result.concat(aplainar(element))
		}
	})
    return result
}

aplainar([1, [2], [3, [[4]]]]);

Invertendo uma string

function inverter(str) {
	if (str.length === 0) return ''
    return str[str.length - 1] + inverter(str.substr(0, str.length - 1))
}

inverter('abcdefg');

Quicksort

function quickSort(arr, lo, hi) {
	if (lo === undefined) lo = 0
    if (hi === undefined) hi = arr.length - 1
    if (lo < hi) {    // fazer o particionamento do array
    	var p = partition(arr, lo, hi)
        console.log('partição de, ' + lo + ' até ' + hi + '=> partition: ' + p)    // ordenar os subarrays
        quickSort(arr, lo, p - 1)
        quickSort(arr, p + 1, hi)  
    }  // para a chamada inicial, retornar um array ordenado
    if (hi - lo === arr.length - 1) return arr
}

function partition(arr, lo, hi) {  
	// seleciona o último elemento como pivot
	var pivot = arr[hi]  
    // rastreia o index onde colocar o pivot  
    var pivotLocation = lo  
    // percorre o subarray e se element <= pivot, coloca element antes do pivot  
    for (var i = lo; i < hi; i++) {
    	if (arr[i] <= pivot) {
        	swap(arr, pivotLocation, i)
            pivotLocation++
        }
    }
    swap(arr, pivotLocation, hi)
    return pivotLocation
}

function swap(arr, index1, index2) {
	if (index1 === index2) return
    var temp = arr[index1]
    arr[index1] = arr[index2]
    arr[index2] = temp
    console.log('trocados' + arr[index1], arr[index2], +' em ', arr)  
    return arr
}

quickSort([1, 4, 3, 56, 9, 8, 7, 5])

Praticar técnicas de recursão é importante. Para estruturas de dados aninhadas como árvores, gráficos e pilhas, a recursão é inestimável.

Em um artigo futuro, discutirei otimização das chamada da cauda (em inglês, tail-call), técnicas de memoização e como elas se relacionam à recursão.

Agradeço por ter me acompanhado até aqui!

Recursos complementares

Wikipédia

Software Engineering (em inglês)

Outro artigo interessante (em inglês)

Material de curso aberto (gratuito) da M.I.T. (em inglês)