Сумма первых n натуральных чисел рекурсией
Задача
Дано натуральное число n. Требуется найти сумму первых n натуральных чисел с помощью рекурсивной функции.
Примеры:
- n = 5 → 1 + 2 + 3 + 4 + 5 = 15
- n = 7 → 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28
- n = 6 → 1 + 2 + 3 + 4 + 5 + 6 = 21
Идея рекурсии (коротко)
Рекурсия — это когда функция вызывает саму себя. В рекурсивном алгоритме обязательно есть базовый случай (останавливает рекурсию) и шаг рекурсии (уменьшает задачу). Здесь базовый случай — n <= 1, шаг рекурсии — добавить n к сумме первых n-1 чисел.
Краткая формулировка:
- Базовый случай: если n <= 1, вернуть n.
- Рекурсивный шаг: вернуть n + findSum(n - 1).
Псевдокод
findSum(n):
if n <= 1 then
return n
else
return n + findSum(n - 1)Альтернативы (быстро)
- Формула: n * (n + 1) / 2 — O(1) по времени и памяти.
- Итеративный цикл: суммировать от 1 до n — O(n) по времени, O(1) по памяти.
- Хвостовая рекурсия с аккумулятором — может быть оптимизирована компилятором/интерпретатором в некоторых языках.
Важно: для больших n рекурсия может привести к переполнению стека. Формула безопаснее и быстрее.
Сложность
- Время: O(n) для рекурсивного и итеративного решений.
- Память: O(n) из-за глубины рекурсии (стек вызовов). Формула — O(1).
Примеры реализации
Ниже приведены реализации, соответствующие псевдокоду. Комментарии и форматирование улучшены для чтения.
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: 21Python
# 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: 21C
// 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;
} Вывод тот же, что и в других примерах.
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;
console.log("n1:", n1);
console.log("n2:", n2);
console.log("n3:", n3);
console.log("Sum of first", n1, "natural numbers:", findSum(n1));
console.log("Sum of first", n2, "natural numbers:", findSum(n2));
console.log("Sum of first", n3, "natural numbers:", findSum(n3));В браузере можно использовать document.write, но для отладки удобнее console.log.
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));
}
}Когда рекурсия не подходит
- Большие n: глубина рекурсии может превысить лимит стека и привести к ошибке.
- Требуется максимально быстрое решение: формула n*(n+1)/2 быстрее и экономичнее.
- Среда без оптимизации хвостовой рекурсии: хвостовая реализация может не дать преимуществ.
Важно: для задач, где n может быть миллионами, используйте формулу или итерацию.
Набор тестов и критерии приёмки
Тесты (вход → ожидаемый результат):
- 0 → 0
- 1 → 1
- 5 → 15
- 10 → 55
- отрицательное n (по соглашению) → либо 0, либо ошибка — нужно определить поведение заранее
Критерии приёмки:
- Функция корректно обрабатывает n >= 0.
- Для n в пределах целесообразной глубины стека программа возвращает правильный результат.
- Для больших n документация указывает альтернативный метод (формула).
Практические подсказки и эвристики
- Всегда реализуйте базовый случай первым; это предотвращает бесконечную рекурсию.
- Тестируйте на граничных значениях: 0, 1 и максимально допустимом n.
- Если язык поддерживает оптимизацию хвостовой рекурсии, используйте аккумулятор.
- Для алгоритмических интервью уместно показать и рекурсивное, и формульное решение.
Краткая терминология
- Рекурсия — метод, когда функция вызывает саму себя.
- Базовый случай — условие, при достижении которого рекурсия останавливается.
- Глубина рекурсии — количество вложенных вызовов; влияет на потребление стека.
Итог
Рекурсивное решение для суммы первых n натуральных чисел просто и наглядо: findSum(n) = n + findSum(n-1) с базовым случаем n <= 1. Однако для практических задач предпочтительнее формула n*(n+1)/2 из-за фиксированной сложности и отсутствия риска переполнения стека.
Важно: выбирайте метод в зависимости от требований по производительности и пределов входных данных.
Автор
Редакция
