Fundamentos de recursividad

Parte de la sección Fundamentals del Journey de C de Coddy — lección 50 de 63.

La recursividad es una técnica en la que una función se llama a sí misma para resolver un problema. Es como resolver un gran problema dividiéndolo en problemas más pequeños y similares.

Veamos una función recursiva simple que calcula el factorial:

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 función recursiva necesita:

Un caso base para detener la recursividad
Un caso recursivo que se acerque al caso base

Por ejemplo, calculando factorial(3):

factorial(3) llama a factorial(2)
factorial(2) llama a factorial(1)
factorial(1) devuelve 1 (caso base)

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

Desafío

Fácil

Crea una función llamada sumToN que utilice recursividad para calcular la suma de los números del 1 al n.

Por ejemplo:

sumToN(3) debería devolver 6 (1 + 2 + 3)
sumToN(5) debería devolver 15 (1 + 2 + 3 + 4 + 5)

Tu función debería:

Usar un caso base cuando n sea 1 (devolver 1)
De lo contrario, devolver n más la suma de los números del 1 al (n-1)

Hoja de referencia

La recursividad es una técnica en la que una función se llama a sí misma para resolver un problema dividiéndolo en problemas más pequeños y similares.

Toda función recursiva necesita:

Un caso base para detener la recursividad
Un caso recursivo que se acerque al caso base

Ejemplo - función factorial:

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

Cómo se ejecuta factorial(3):

factorial(3) llama a factorial(2)
factorial(2) llama a factorial(1)
factorial(1) devuelve 1 (caso base)
factorial(2) devuelve 2 * 1 = 2
factorial(3) devuelve 3 * 2 = 6

Pruébalo tú mismo

#include <stdio.h>

// Escribe tu función sumToN aquí

// No cambies la función main()
int main() {
    int n;
    scanf("%d", &n);
    
    printf("%d", sumToN(n));
    return 0;
}

Ponte a prueba

Esta lección incluye un breve cuestionario. Empieza la lección para responderlo y registrar tu progreso.

Todas las lecciones de Fundamentals

1Introducción

Lenguaje C ¡Hola Mundo!Comentarios Estructura básica de un programa

4Flujo de control

Sentencia If If - Else Else-If Switch Case Operador condicional ternario Desafío de repaso If - Else anidados

7Funciones

Declarar una función Tipos de retorno Parámetros Desafío de repaso n.º 1Fundamentos de recursividadPrototipos de funciones Desafío de repaso n.º 2