Fundamentos da Recursão

Parte da seção Fundamentals do Journey de C da Coddy — lição 50 de 63.

Recursão é uma técnica onde uma função chama a si mesma para resolver um problema. É como resolver um grande problema ao dividi-lo em problemas menores e semelhantes.

Vamos dar uma olhada em uma função recursiva simples que calcula o fatorial:

int factorial(int n) {
    // Base case: factorial of 0 or 1 is 1
    if (n <= 1) {
        return 1;
    }
    
    // Recursive case: n! = n * (n-1)!
    return n * factorial(n - 1);
}

Toda função recursiva precisa de:

Um caso base para interromper a recursão
Um caso recursivo que se aproxima do caso base

Por exemplo, calculando factorial(3):

factorial(3) chama factorial(2)
factorial(2) chama factorial(1)
factorial(1) retorna 1 (caso base)

factorial(2) retorna 2 * 1 = 2
factorial(3) retorna 3 * 2 = 6

Desafio

Fácil

Crie uma função chamada sumToN que use recursão para calcular a soma dos números de 1 a n.

Por exemplo:

sumToN(3) deve retornar 6 (1 + 2 + 3)
sumToN(5) deve retornar 15 (1 + 2 + 3 + 4 + 5)

Sua função deve:

Usar um caso base quando n for 1 (retornar 1)
Caso contrário, retornar n mais a soma dos números de 1 a (n-1)

Folha de consulta

Recursão é uma técnica onde uma função chama a si mesma para resolver um problema, dividindo-o em problemas menores e semelhantes.

Toda função recursiva precisa de:

Um caso base para interromper a recursão
Um caso recursivo que se aproxima do caso base

Exemplo - função fatorial:

int factorial(int n) {
    // Caso base: o fatorial de 0 ou 1 é 1
    if (n <= 1) {
        return 1;
    }
    
    // Caso recursivo: n! = n * (n-1)!
    return n * factorial(n - 1);
}

Como factorial(3) é executado:

factorial(3) chama factorial(2)
factorial(2) chama factorial(1)
factorial(1) retorna 1 (caso base)
factorial(2) retorna 2 * 1 = 2
factorial(3) retorna 3 * 2 = 6

Experimente você mesmo

#include <stdio.h>

// Escreva sua função sumToN aqui

// Não altere a função main()
int main() {
    int n;
    scanf("%d", &n);
    
    printf("%d", sumToN(n));
    return 0;
}

Teste seus conhecimentos

Esta lição inclui um quiz rápido. Comece a lição para respondê-lo e acompanhar seu progresso.

Todas as lições de Fundamentals

1Introdução

Linguagem C Olá Mundo!Comentários Estrutura Básica de um Programa

4Fluxo de Controle

Instrução If If - Else Else-If Switch Case Operador Condicional Ternário Desafio de Revisão If - Else Aninhado

7Funções

Declarar uma Função Tipos de Retorno Parâmetros Desafio de Recapitulação nº 1Fundamentos da RecursãoProtótipos de Função Desafio de Recapitulação nº 2