Função Recursiva em C++

Neste tutorial de C++, vamos aprender a famosa e importante arte da recursividade, e você vai entender a piadinha de programadores: "Para saber recursão, tem que saber recursão"

Função Recursiva

Nos programadores que fizemos no decorrer de nossos tutoriais, fizemos com que, várias vezes, uma função fosse chamada dentro da outra. Recursão tem a ver com invocar uma função.

Mas ela chama uma função em especial. A função recursiva nada mais é a função que chama ela mesma.

Vamos criar uma função que exibe uma mensagem na tela e depois invoca ela mesma:

#include <iostream>
using namespace std;

void recur()
{
    cout<<"Progressive C++ course"<<endl;
    recur();
}

int main()
{
    recur();
    return 0;
}

Acontece o seguinte:

E é bem simples de entender...invocamos a recur(), ela exibe uma mensagem na tela e ... chama ela novamente, que ao ser chamada, exibe uma mensagem na tela...depois chama ela novamente, que exibe uma mensagem...e assim vai, indefinidamente, para o infinito e além.

Pra parar, tive que dar um Control+C, senão ficava rodando pra sempre.

Como usar recursão com funções

Desse jeito, as funções recursivas não são tão úteis.
Para aprender como usar elas da maneira correta, precisamos de uma espécie de contador, assim como fizemos com os loopings.

Vamos fazer com que a recur() receba um inteiro, e só vai chamar ela mesmo se esse inteiro for maior que 0:

#include <iostream>
using namespace std;

void recur(int counter)
{
    if(counter>0){
        cout<<"Curso C++ Progressivo"<<endl;
        recur(counter-1);
    }
}

int main()
{
    recur(5);
    return 0;
}

Se o número recebido for maior que 0, exibimos a mensagem e chamamos novamente a recur(), porém, vamos passar um argumento menor, subtraído de 1, pois essa função já executou uma vez.

Assim, se você fizer recur(5), ela vai rodar a função 5 vezes apenas:

1. Primeiro chamamos recur(5), exibiu a mensagem e chamou recur(4).
2. recur(4) exibe a mensagem e chama recur(3).
3. recur(3) exibe a mensagem e chama recur(2).
4. recur(2) exibe a mensagem e chama recur(1)
5. recur(1) exibe a mensagem e chama recur(0).

Quando chamamos recur(0), nada é feito e nenhuma função é mais invocada, encerrando a recursão.

recur(0) é o caso base, onde ela deve parar.
Vamos praticar e ver como aplicar a técnica da recursividade com funções, em C++?

Somatório com recursão

Vamos chamar de sum(n) o somatório do valor n.

Por exemplo:
sum(5) =  5 + 4 + 3 + 2 + 1

Mas sum(4) = 4 + 3 + 2 + 1

Ou seja: sum(5) = 5 + sum(4)

Podemos generalizar fazendo:
sum(n) = n + sum(n-1)

Veja que tem uma recursão aí. A sum() está chamando a sum(), com um argumento decrementado em 1, mas está. Quando o argumento for 1, ele deve retornar 1 (pois somatório de 1 é 1) e parar de invocar a função de somatório.

Nosso código fica:

#include <iostream>
using namespace std;

int sum(int num)
{
    if(num==1)
        return 1;
    else
        return num+sum(num-1);
}

int main()
{
    int num;

    cout<<"Somatório de: ";
    cin>> num;

    cout<<"Igual a: "<<sum(num)<<endl;
}

sum(1) é o caso base, onde resolvemos as coisas manualmente, sem usar recursão, apenar retornando 1.
Bacana. né?

Fatorial com recursão

Vamos chamar de fat(n) o fatorial do valor n.
fat(n) = n * (n-1) * (n-2) * ... 3 * 2 * 1

Ou seja:
fat(n) = n * fat(n-1)

Concorda?
Temos aí uma lógica com recursividade. A função fat() chamando a fat().
Ela deve chamar até chegar no argumento 1, e fatorial de 1 é 1.

Veja como fica nosso código:

#include <iostream>
using namespace std;

int fat(int num)
{
    if(num==1)
        return 1;
    else
        return num*fat(num-1);
}

int main()
{
    int num;

    cout<<"Fatorial de: ";
    cin>> num;

    cout<<"Igual a: "<<fat(num)<<endl;
}

fat(1) é o caso base, onde não invocamos a recursividade, e sim retornamos diretamente um valor.

Sequência de Fibonacci com recursividade

Por fim, nosso bom e velho Fibonacci.
Relembre aqui o que é a série de Fibonacci.

Basicamente, os dois primeiros termos são 0 e 1. São nossos casos base.
O terceiro termo, em diante, é a soma dos dois anteriores. Ou seja:
F(1) = 0
F(2) = 1
F(3) = F(2) + F(1) = 1 + 0 = 1
F(4) = F(3) + F(2) = 1 + 1 = 2
F(5) = F(4) + F(3) = 2 + 1 = 3
F(6) = F(5) + F(4) = 3 + 2 = 5
F(7) = F(6) + F(5) = 5 + 3 = 8
...

Ou seja, a fórmula para achar o termo 'n' é:
F(n) = F(n-1) + F(n-2)
Você concorda ?

Quando o argumento de nossa função receber o valor 2, ou seja, quando quisermos saber o valor de F(2), a função deve retornar 1. E quando quisermos saber o valor de F(1), a função deve retornar 1.
Não devemos calcular usando a fórmula da recursividade, pois seria calculado:
F(2) = F(1) + F(0)
F(1) = F(0) + F(-1)

E não existem se deve calcular F(0) quando mais F(1).
Assim, nosso código fica:

#include <iostream>
using namespace std;

int fibo(int num)
{
    if(num==1)
        return 0;
    else
        if(num==2)
            return 1;
        else
            return fibo(num-1)+fibo(num-2);
}

int main()
{
    int num;

    cout<<"Termo: ";
    cin>> num;

    cout<<"Igual a: "<<fibo(num)<<endl;
}

Teste. Calcule o termo 19 da sequência, ele é 2584. Deu certo?

Recursão x Iteração

Recursão é uma ferramenta que pode salvar nossa vida, como programador, muitas vezes, pois a ideia por trás do 'uma função chamar ela mesma' é bem simples, útil e pode ser empregada nos mais diversos tipos de problemas que sejam repetitivos, que sigam determinados padrões, como os exemplos acima vistos.

Mas é importante salientar que tudo que é feito com recursão, é possível fazer sem.
Mais especificamente, tudo que é possível fazer com recursão, você pode usar iteração, com loopings.

Quando invocamos uma função, muita coisa ocorre por debaixo dos panos. Muita memória é alocada para os parâmetros e argumentos, o endereço e o código da função são alocados, armazenados e acessados em locais pré-definidos na memória, o local onde ela foi invocada é salvo também, para voltar pra lá quando terminar a execução, e por ai vai.

Isso resulta em uma coisa: recursão é mais lento que iteração. de um modo geral.
Então, por que usar recursão? Simples, alguns problemas, de lógica repetitiva, são beeeem mais simples de serem resolvidos usando recursão.

Embora seja mais lenta e menos eficiente, você pode compensar isso resolvendo/criando um algoritmo em menos tempo, usando recursão. Você pode facilmente descobrir a solução de um problema aplicando recursividade, e as vezes iteração pode ser mais complicado de programar.

O segredo da recursividade é que ela transforma um problema em um problema menor, mas similar.
Em vez de resolver func(n), você só precisa resolver para func(n-1), depois func(n-2)....func(3)...func(2)...e geralmente pra resolver coisas com argumentos pequenos, nós sabemos resolver facilmente. Recursividade faz isso: transforma um problema em um probleminha, com a exata mesma lógica.

Voltaremos a usar recursão para calcular, por exemplo, caracteres na seção de strings e também com listas.

Exercício de C++

Crie uma função para calcular o fatorial de um número, usando recursão. Escolha um número bem grande, que leve alguns segundos de sua máquina. Veja quanto tempo demorou pra fazer a operação.
Agora crie outra função para calcular o mesmo fatorial, mas usando iteração (Fatorial com laços em C++), calcule o mesmo número. Anote o tempo.

Agora compartilhe com a gente, nos comentários: que número calculou e quanto tempo cada função levou pra calcular?