Сумма первых n натуральных чисел рекурсией

TL;DR

Кратко: существует простой рекурсивный приём, который вычисляет сумму первых n натуральных чисел через формулу S(n)=n+S(n-1) с базовым случаем n<=1. Для практики показаны реализации на C++, Python, C, JavaScript и Java. Для больших n итеративная формула n*(n+1)/2 проще и безопаснее по стеку.

Человек за работой и логотипы языков C, C++, Python, Java и JavaScript

Рекурсия — это подход, при котором функция вызывает сама себя прямо или косвенно. Рекурсивные алгоритмы часто применяют, чтобы разбить сложную задачу на более простые.

Решая простые задачи, такие как произведение двух чисел или сумма первых n чисел, вы лучше поймёте принципы рекурсии.

В этой статье вы научитесь находить сумму первых n натуральных чисел с помощью рекурсии, увидите код на нескольких языках и получите рекомендации, когда лучше не использовать рекурсию.

Постановка задачи

Вам дано натуральное число n. Нужно найти сумму первых n натуральных чисел, используя рекурсию.

Примеры:

Пример 1: n = 5
Сумма = 1 + 2 + 3 + 4 + 5 = 15 → вывод 15.
Пример 2: n = 7
Сумма = 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28 → вывод 28.
Пример 3: n = 6
Сумма = 1 + 2 + 3 + 4 + 5 + 6 = 21 → вывод 21.

Рекурсивная функция: идея и псевдокод

Большинство рекурсивных функций имеют простую структуру: базовый случай и рекурсивный шаг.

FUNCTION name  
    IF condition THEN  
        RETURN result  
    ELSE  
        CALL FUNCTION name  
END FUNCTION

Для задачи суммы первых n чисел наблюдение простое: сумма первых n чисел равна n плюс сумма первых n-1 чисел. Псевдокод:

findSum(n):  
    IF n<=1 THEN  
        RETURN n  
    ELSE  
        RETURN n + findSum(n-1)  
END FUNCTION

Теперь можно реализовать этот псевдокод на любом языке.

Важно: есть математическая формула, дающая ответ за O(1): S = n * (n + 1) / 2. Эта формула экономит время и память и предпочтительна при больших n.

C++ — реализация рекурсивной суммы

Ниже показана реализация на C++:

// C++ implementation to find the sum of  
// first n natural numbers using recursion  
#include   
using namespace std;  
  
// Recursive function to find the sum of first n natural numbers  
int findSum(int n)  
{  
 if (n<=1)  
 {  
 return n;  
 }  
 else  
 {  
 return n + findSum(n-1);  
 }  
}  
  
// Driver code  
int main()  
{  
 int n1 = 5, n2 = 7, n3 = 6;  
  
 cout << "n1: " << n1 << endl;  
 cout << "n2: " << n2 << endl;  
 cout << "n3: " << n3 << endl;  
  
 cout << "Sum of first " << n1 << " natural numbers: " << findSum(n1) << endl;  
 cout << "Sum of first " << n2 << " natural numbers: " << findSum(n2) << endl;  
 cout << "Sum of first " << n3 << " natural numbers: " << findSum(n3) << endl;  
  
return 0;  
}

Вывод:

n1: 5   
n2: 7   
n3: 6   
Sum of first 5 natural numbers: 15   
Sum of first 7 natural numbers: 28   
Sum of first 6 natural numbers: 21

Python — реализация рекурсивной суммы

Реализация на Python:

# Python implementation to find the sum of  
# first n natural numbers using recursion  
  
# Recursive function to find the sum of first n natural numbers  
def findSum(n):  
    if n<=1:  
        return n  
    else:  
        return n + findSum(n-1)  
  
# Driver Code  
n1 = 5  
n2 = 7  
n3 = 6  
  
print("n1: ", n1)  
print("n2: ", n2)  
print("n3: ", n3)  
  
print("Sum of first ", n1, " natural numbers: ", findSum(n1))  
print("Sum of first ", n2, " natural numbers: ", findSum(n2))  
print("Sum of first ", n3, " natural numbers: ", findSum(n3))

Вывод:

n1: 5   
n2: 7   
n3: 6   
Sum of first 5 natural numbers: 15   
Sum of first 7 natural numbers: 28   
Sum of first 6 natural numbers: 21

C — реализация рекурсивной суммы

Реализация на C:

// C implementation to find the sum of  
// first n natural numbers using recursion  
#include   
  
// Recursive function to find the sum of first n natural numbers  
int findSum(int n)  
{  
 if (n<=1)  
 {  
 return n;  
 }  
 else  
 {  
 return n + findSum(n-1);  
 }  
}  
  
// Driver code  
int main()  
{  
 int n1 = 5, n2 = 7, n3 = 6;  
  
 printf("n1: %d \n", n1);  
 printf("n2: %d \n", n2);  
 printf("n3: %d \n", n3);  
  
 printf("Sum of first %d natural numbers: %d \n", n1, findSum(n1));  
 printf("Sum of first %d natural numbers: %d \n", n2, findSum(n2));  
 printf("Sum of first %d natural numbers: %d \n", n3, findSum(n3));  
  
return 0;  
}

Вывод:

n1: 5   
n2: 7   
n3: 6   
Sum of first 5 natural numbers: 15   
Sum of first 7 natural numbers: 28   
Sum of first 6 natural numbers: 21

JavaScript — реализация рекурсивной суммы

Реализация на JavaScript (браузерный пример):

// JavaScript implementation to find the sum of  
// first n natural numbers using recursion  
  
// Recursive function to find the sum of first n natural numbers  
function findSum(n) {  
 if (n<=1) {  
 return n;  
 } else {  
 return n + findSum(n-1);  
 }  
}  
  
  
// Driver Code  
var n1 = 5, n2 = 7, n3 = 6;  
  
document.write("n1: " + n1 + "\n");  
document.write("n2: " + n2 + "\n");  
document.write("n3: " + n3 + "\n");  
  
document.write("Sum of first " + n1 + " natural numbers: " + findSum(n1) + "\n");  
document.write("Sum of first " + n2 + " natural numbers: " + findSum(n2) + "\n");  
document.write("Sum of first " + n3 + " natural numbers: " + findSum(n3) + "\n");

Вывод (в документе):

n1: 5   
n2: 7   
n3: 6   
Sum of first 5 natural numbers: 15   
Sum of first 7 natural numbers: 28   
Sum of first 6 natural numbers: 21

Java — реализация рекурсивной суммы

Реализация на Java:

// Java implementation to find the sum of  
// first n natural numbers using recursion  
public class Main  
{  
 // Recursive function to find the sum of first n natural numbers  
 public static int findSum(int n)  
 {  
 if (n <= 1)  
 {  
 return n;  
 }  
 else  
 {  
 return n + findSum(n - 1);  
 }  
 }  
  
// Driver code  
 public static void main(String[] args)  
 {  
 int n1 = 5, n2 = 7, n3 = 6;  
 System.out.println("n1: " + n1);  
 System.out.println("n2: " + n2);  
 System.out.println("n3: " + n3);  
  
 System.out.println("Sum of first " + n1 + " natural numbers: " + findSum(n1));  
 System.out.println("Sum of first " + n2 + " natural numbers: " + findSum(n2));  
 System.out.println("Sum of first " + n3 + " natural numbers: " + findSum(n3));  
 }  
}

Вывод:

n1: 5   
n2: 7   
n3: 6   
Sum of first 5 natural numbers: 15   
Sum of first 7 natural numbers: 28   
Sum of first 6 natural numbers: 21

Когда рекурсия не подходит

Большие n могут привести к переполнению стека. Рекурсивный алгоритм использует стек вызовов — для глубины вызова порядка десятков тысяч стек может исчерпаться.
Если требуется максимальная производительность и минимальная память, лучше использовать формулу n*(n+1)/2 (O(1)).
В средах с жёстким ограничением глубины рекурсии (встроенные среды, некоторые интерпретаторы) рекурсия опасна.

Important: для этой задачи итеративная формула даёт тот же результат без риска переполнения стека.

Альтернативные подходы

Формула: S = n * (n + 1) / 2 — лучше по сложности и по использованию памяти.
Итеративный цикл (for/while) — O(n) по времени, O(1) по памяти, без проблем со стеком.
Хвостовая рекурсия — в языках с оптимизацией хвостовой рекурсии (TR) можно переписать функцию в хвостовую форму, чтобы избежать роста стека.

Пример хвостовой формы (псевдокод):

findSumTail(n, acc):
    IF n<=0 THEN
        RETURN acc
    ELSE
        RETURN findSumTail(n-1, acc+n)

Ментальные модели и эвристики

Разделяй и властвуй: если задачу можно выразить через меньшие подзадачи того же типа, рекурсия подходит.
Всегда думайте о базовом случае — от него зависит корректность и завершение.
Оценивайте глубину рекурсии заранее; если она пропорциональна входу и вход может быть большим, рассматривайте итерацию.

Факто-бокс

Сложность рекурсивной версии: O(n) по времени, O(n) по стеку.
Сложность формулы: O(1) по времени, O(1) по памяти.
Подходит для обучения и демонстрации рекурсивного мышления; для промышленного применения формула зачастую предпочтительнее.

Критерии приёмки

Функция корректно возвращает сумму для n ≥ 1.
Функция корректно обрабатывает граничные случаи (например, n = 0, если это предусмотрено).
Для языков со статической типизацией — корректные типы; при больших n — отсутствие переполнения целого типа или указание на риск.

Чек-лист по ролям

Разработчик: протестировать на нескольких значениях n (включая 0, 1, края и средние значения).
Ревьювер: проверить базовый случай, корректность возврата, и обработку негативных или нулевых n.
DevOps/инженер по надёжности: оценить риск переполнения стека для реальных входных данных; при необходимости ограничить вход или заменить реализацию.

Краткая заметка для анонса (100–200 слов)

Реализация суммы первых n натуральных чисел через рекурсию — классическая образовательная задача, которая помогает понять базовый случай и рекурсивный шаг. В статье показаны решения на C++, Python, C, JavaScript и Java, а также пояснена математическая формула n*(n+1)/2, которая даёт ответ за константное время. Для практики рекомендую реализовать и рекурсивную, и итеративную версии, а затем сравнить по использованию памяти и по времени. Обратите внимание на ограничение глубины рекурсии в вашей среде — для производственных задач формула или итерация обычно предпочтительнее.

Короткое резюме

Рекурсивная формула: S(n) = n + S(n-1) с базовым случаем n<=1.
Для больших n используйте формулу n*(n+1)/2 или итерацию, чтобы избежать проблем со стеком.
Код на нескольких языках приведён выше для быстрого копирования и проверки.

Спасибо за внимание — практикуйтесь, проверяйте граничные случаи и выбирайте инструмент (рекурсия или формула) по задаче.