Recursão

Introdução

Recursão é um dos conceitos mais importantes da ciência da computação, e extremamente divertido de se pensar sobre. Basicamente, trata-se de uma função chamando a si mesma. Insano, né? Vamos usar uma analogia com o mundo real para ficar mais claro, imagine um cenário em que você chama seus amigos para sair.

Você liga para a gabs, chama ela para sair, mas ela diz que só vai se a gheysa for, então ela coloca a ligação em espera e liga para a gheysa.

A gheysa fala que só vai se o café for, então ela coloca a ligação em espera e liga para o café.

O café fala que só vai se o normando for, então ele coloca a ligação em espera e liga para o normando.

O normando fala que só vai se o eth for, então ele coloca a ligação em espera e liga para o eth.

O eth aceita ir e então desliga a ligação.

O normando retorna a ligação com o café, aceita e desliga a ligação.

O café retorna a ligação com a gheysa, aceita ir e desliga a ligação.

A gheysa retorna a ligação com a gabs, aceita ir e desliga a ligação.

A gabs retorna a ligação com você, aceita ir e pronto vocês todos vão sair!

Codificando o Conceito

Note que, no nosso exemplo acima, pôr a ligação em espera e chamar outra pessoa é justamente o ato de uma função chamar a si mesma, vamos visualizar isso em código:

def call_for_lunch(person):
    if person == 'eth': # BASE CASE
        return True
    return call_for_lunch(next_person) # RECURSIVE CALL

Nesse exemplo, nós vemos as duas coisas essenciais para compor uma função recursiva:

1. Uma base call, onde a função retornará algum valor e não chamará a si própria novamente (caso contrário, teríamos um looping infinito)

2. Uma recursive call, onde a função chama a si mesma caso ela ainda não tenha chegado na base call

Aqui uma clássica função recursiva para calcular o fatorial:

def factorial(n):
    if n <= 1: # BASE CASE
        return 1
    return n * factorial(n - 1) # RECURSIVE CALL

Você pode abrir o pythontutor para ver a stack da recursão se formando e sendo resolvida no código acima.

Recursão e Stack

Como o computador consegue fazer uma função chamar a si mesma? Simples, ele utiliza uma stack nos bastidores para ter uma noção de onde as coisas estão.

A stack interna de um computador é chamada de "call stack", e os dados que são colocados em uma call stack são chamados de stack frames".

fonte: Recursion Review, AlgoMonster.

keywords: recursão, call stack, stack frame