Noções Básicas de Recursão

Parte da seção Fundamentos do Journey de C da Coddy. Lição 50 de 63.

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

Vamos analisar uma função recursiva simples que calcula o fatorial:

int factorial(int n) {
    // Caso base: fatorial de 0 ou 1 é 1
    if (n <= 1) {
        return 1;
    }
    
    // Caso recursivo: 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 avance em direção ao 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)

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 Fundamentos

1Introdução

Linguagem C Olá, mundo!Comentários Estrutura básica do 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

Declare uma Função Tipos de Retorno Parâmetros Desafio de Revisão nº 1Noções Básicas de RecursãoProtótipos de Função Desafio de Revisão nº 2

Pratique por conta própria: Compilador de C online