Sum of natural numbers using recursion in C
In this article, we will find the sum of natural numbers using recursion in C programming. But before finding the sum, we must know about the natural number, algorithm, program, and its output.
What are natural numbers?
Natural numbers are the counting numbers that start from 1 and continue indefinitely without any upper limit. They do not include negative numbers or fractions; only whole positive numbers are part of the set of natural numbers.
![Sum of natural numbers using recursion in C](https://static.tutorialandexample.com/c/sum-of-natural-numbers-using-recursion-in-c1.png)
Algorithm:
The algorithm for finding the sum of natural numbers using recursion in C:
- Create the "NaturalNumberSum" recursive function with an integer parameter n.
- Verify the base case: If n equals 0, return zero because the sum of all natural integers from 1 to 0 is zero.
- If n is not 0, recursively call the "NaturalNumberSum" function with n-1 and store the result in a variable "Sum".
- Add n to "Sum" and return the result.
![Sum of natural numbers using recursion in C](https://static.tutorialandexample.com/c/sum-of-natural-numbers-using-recursion-in-c2.png)
Let us see with an example:
![Sum of natural numbers using recursion in C](https://static.tutorialandexample.com/c/sum-of-natural-numbers-using-recursion-in-c3.png)
Code:
#include <stdio.h>
//Function to calculate the sum of natural numbers using recursion
int NaturalNumbersSum(int n) {
if (n == 0) {
return 0; // Base case: If n is 0, return 0
} else {
return n +NaturalNumbersSum(n - 1); // Recursively call the function with n-1
}
}
int main() {
int num;
//inputting the value that number indicates upto which the program should sum.
printf("Enter a positive integer: ");
scanf("%d", &num);
//checking whether the number is positive or not
if (num < 1) {
printf("Please enter a positive integer.\n");
} else {
int sum = NaturalNumbersSum(num);
printf("Sum of first %d natural numbers is %d\n", num, sum);
}
return 0;
}
Output:
![Sum of natural numbers using recursion in C](https://static.tutorialandexample.com/c/sum-of-natural-numbers-using-recursion-in-c4.png)
Time complexity and space complexity:
The time complexity of this function is O(n), where n is the given input number n1. It is because the function makes n recursive calls, each with a constant time complexity of O(1).
The space complexity of this function is also O(n), because the function creates n activation records on the call stack, one for each recursive call.