# 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.



<figure><img src="https://3099726359-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FPoUhR6ITF2wdty5CdTAc%2Fuploads%2F4mGfyjGdF3chFxN7UEhb%2Frecursion.jpg?alt=media&#x26;token=7abbf270-e3a0-4f59-af70-31b96f1e9be6" alt=""><figcaption></figcaption></figure>

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:\


```python
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:

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

Você pode abrir o [pythontutor](https://pythontutor.com/) para ver a stack da recursão se formando e sendo resolvida no código acima.&#x20;

### 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.&#x20;

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"**. &#x20;





fonte: Recursion Review, AlgoMonster.

keywords: recursão, call stack, stack frame
