Como calcular o somatório de 1 até n com recursão?

Nesta aula vamos aprender como calcular o somatório de 1 até n com recursão. Este é um exercício bem simples quando resolvido sem recursão, bastando uma repetição de 1 até n somando esses valores. Vamos então resolver este somatório de 1 até n com uma função recursiva?

Como já vimos nas aulas anteriores, encontrar o ponto de parada ou o caso base é fundamental em qualquer recursão e neste caso não poderia ser diferente.

A sequência que queremos somar é crescente (1 até n) mas não precisamos iniciar a soma em 1. Fazer isso vai tornar nosso processo de parada mais complicado. Podemos iniciar a soma em n e ir decrementando o valor a ser somado. Dessa forma podemos usar o 0 como nosso ponto de parada, afinal zero é zero!

Seguindo estes passos nossa função recursiva se torna muito simples. Se for zero, então retornamos zero. Caso contrário, retornamos n mais o retornado na chamada recursiva de n – 1, assim:

int soma(int n){
    if(n == 0)
        return 0;
    else
        return n + soma(n - 1);
}

Lembra da pilha de recursão? Imagine que o usuário digite o valor 5. Como 5 é diferente de zero, então teremos nossa primeira chamada recursiva empilhando o valor de n.

pilha -> 5 + soma(4)

Como 4 também é diferente de zero, novamente teremos outro empilhamento com outra chamada recursiva. Isso irá se repetir até n chegar a zero. Nosso pilha ficará assim:

pilha -> 1 + soma(0)
pilha -> 2 + soma(1)
pilha -> 3 + soma(2)
pilha -> 4 + soma(3)
pilha -> 5 + soma(4)

Ao fazer a última chamada recursiva, com n = 0, não teremos novas chamadas recursivas e é retornado o valor 0. Esse valor é retornado exatamente para o ponto onde foi feita a chamada recursiva com n = 0 e o computador começa então o processo de desempilhar.

pilha -> 1 + 0
pilha -> 2 + soma(1)
pilha -> 3 + soma(2)
pilha -> 4 + soma(3)
pilha -> 5 + soma(4)

Como agora o computador já conhece os dois valores envolvidos na soma, a operação é realizada e novamente o resultado é retornado para o ponto onde foi feito a chamada com n = 1.

pilha -> 2 + 1
pilha -> 3 + soma(2)
pilha -> 4 + soma(3)
pilha -> 5 + soma(4)

Novamente a soma é realizada e o resultado retornado.

pilha -> 3 + 3
pilha -> 4 + soma(3)
pilha -> 5 + soma(4)

Esse processo irá se repetir até realizar a última operação.

pilha -> 5 + 10

Quando a última operação é realizada, o resultado é retornado para o ponto onde foi feita a chamada à função, no nosso exemplo, dentro de um printf na função main, imprimindo assim o resultado na tela.

Código C recursivo para calcular o somatório

#include <stdio.h>
#include <stdlib.h>

/*
        Aula 160: Desenvolva uma função recursivo que calcule a soma dos números inteiros de 1 a N.

        Escrita por Wagner Gaspar
        Março de 2021
*/

int soma(int n){
    if(n == 0)
        return 0;
    else
        return n + soma(n - 1);
}

int main () {

    int n;

    printf("Digite N: ");
    scanf("%d", &n);

    printf("Soma de 1 ate %d: %d\n", n, soma(n));

    return 0;
}

Início