Finding the sum of natural numbers using recursion involves defining a function that recursively adds numbers from 1 to the given limit. The function repeatedly calls itself with decreasing values until reaching the base case, where it returns the sum.

Example:

Input: 5
Output: 15
Explanation: 1 + 2 + 3 + 4 + 5 = 15
Input: 10
Output: 55
Explanation: 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 + 10 = 55

Approach

A simple recursive function for finding the sum of natural numbers repeatedly calls itself with decremented input until reaching the base case. If the input is 1, it returns 1; otherwise, it adds the current input to the result of the function with the input decremented by 1.

Example: The function myFunction recursively calculates the sum of natural numbers up to n. It returns 1 if n is 1; otherwise, it adds n to myFunction(n – 1).

15

Time complexity: O(n)

Space complexity: O(n)