Funções recursivas: pra aprender recursividade, tem que saber recursividade

O título desse artigo em C pode parecer estranho, à primeira vista, mas ao fim do tutorial você entenderá essa ‘piada interna’ entre os programadores.

Neste tutorial de nossa apostila de C, vamos ensinar uma importante técnica: a recursão.

• Leia esse conteúdo Offline: Apostila C Progressivo

Recursividade em C

Uma função que é dita recursiva é aquela que invoca ela mesma.

Já explicamos, e demos exemplos, que é possível, recomendável e normal que uma função invoque outra.

Porém também é possível que uma função chame ela mesma, mas é preciso um cuidado especial para não cairmos em um looping infinito.

Geralmente, para que uma função não fique invocando ela mesma indefinidamente, devemos fazer umas alterações no argumento, ao invocar novamente a função ao passo que devemos definir, na função, testes condicionais sobre o parâmetro para saber onde devemos parar de invocar a função.

Ok, a equipe do curso C Progressivo assume: essa explicação é realmente complicada e todos sentiram dificuldade a primeira vez que a leram.

Mas, como de costume, vamos apresentar diversos exemplos de códigos, bem comentados, para que você possa entender melhor isso na prática.

Exemplo de código usando Recursão

Crie um programa em C que peça um número inteiro ao usuário e retorne a soma de todos os números de 1 até o número que o usuário introduziu ou seja: 1 + 2 + 3 + ... + n

Utilize recursividade.

Vamos criar uma função soma(int n).

Se n=5, essa função deve retornar: soma(5) = 5 + 4 + 3 + 2 + 1

Se n=4, essa função deve retornar: soma(4) = 4 + 3 + 2 + 1

Se n=3, essa função deve retornar: soma(3) = 3 + 2 + 1

E assim por diante. Porém, para fazermos uso da brilhante idéia matemática da recursividade, temos que notar padrões.

Veja que:

soma(5) = 5 + 4 + 3 + 2 +1 = 5 + soma(4)

O mesmo para:

soma(4) = 4 + 3 + 2 + 1 = 4 + soma(3)

Ou seja, temos a fórmula geral:

soma(n) = n + soma(n-1)

Concorda?

Ou seja:

soma(n) = n + soma(n-1) = n + (n-1) + soma(n-2) = n + (n-1) + (n-2) + soma(n-3)...

E onde essa soma para? Para quando o último elemento dessa soma for 1.

Então:

soma(n) = n +(n-1) + (n-2) + (n-3) + .... + 1

Agora vamos traduzir essa fórmula em termos de programação.

A função recebe um número, e a primeira coisa que ela deve fazer é ver se esse valor é 1.

Se for, deve retornar 1, afinal:

soma(1) = 1

E se não for 1, deve retornar:

n + soma(n-1)

Isso é feito da uma maneira muito simples, através de um simples teste condicional do tipo IF ELSE.

Veja como ficou nosso código em C:

#include <stdio.h>
 
int soma(int n)
{
    if(n == 1)
        return 1;
    else
        return ( n + soma(n-1) );
}
 
int main()
{
    int n;
    printf("Digite um inteiro positivo: ");
    scanf("%d", &n);
 
    printf("Soma: %d\n", soma(n));
}

Exemplo de código usando recursão em C

Crie um programa que calcule o fatorial de um número fornecido pelo usuário através da recursividade.

O fatorial de ‘n’ é representado por n!, onde:

n! = n * (n-1) * (n-2)*..1

O raciocínio desse exemplo é análogo ao do exemplo anterior, porém, vamos usar a multiplicação ao invés da soma.

Antes de resolvermos, vamos ver a idéia matemática por trás do fatorial.

Como dissemos na questão, para n=5:

5! = 5 * 4 * 3 * 2 * 1

Para n=4:

4! = 4 * 3 * 2 * 1

Para n=3:

3! = 3 * 2 * 1

E assim sucessivamente.

Porém, note que:

5! = 5 * 4 * 3 * 2 * 1 = 5 * 4!

E também:

4! = 4 * 3 * 2 * 1 = 4 * 3!

Podemos formular uma fórmula geral:

n! = n * (n-1)!

Abrindo esse produto, devemos parar somente quando o último elemento do produto for 1:

n! = n * (n-1)! = n * (n-1) * (n-2)! = n * (n-1) * (n-2) * ... * 1

Para programar isso, criamos uma função fatorial(int n) que retorna 1 se for passado 1 como argumento (pois fatorial(1) = 1) e caso o argumento seja maior que 1:

fatorial(n) = n * fatorial(n-1)

Isso, assim como no exemplo passado, e na maioria das funções usando a idéia de recursividade, é resolvido com um simples teste condicional IF ELSE.

Veja como ficou nosso código em C que calcula o fatorial:

#include <stdio.h>

int fatorial(int n)
{
    if(n == 1)
        return 1;
    else
        return ( n * fatorial(n-1) );
}

int main()
{
    int n;
    printf("Digite um inteiro positivo: ");
    scanf("%d", &n);

    printf("%d! = %d\n", n, fatorial(n));
}

Ou seja, pra calcular a função soma() é preciso usar a função soma().

Pra calcular o fatorial com a função fatorial() é preciso usar a função fatorial().

Entendeu agora o nome dessa lição?