Let’s start from a mathematical approach. I want to write a function that determines the sum of the first n natural numbers. The function would look something like this:
f(n) = 1 + 2 + 3 + . . . n
The most obvious method, but probably not the most efficient, would be to manually compute the sum of the numbers from 1 to n each time. If I were to use this approach, I would be doing A LOT of repeat work.
Let’s think about how the results of previous sums can be used to compute future sums.
f(1) = 1
f(2) = 1 + 2 = f(1) + 2 = 3
f(3) = 1 + 2 + 3 = f(2) = 3 = 6
. . .
f(n) = n + f(n-1) for n > 1
Let’s say the current number is n
. To find the sum of the natural numbers from 1 to n
, I can use the precomputed sum of the natural numbers from 1 to n - 1
and add the n to that sum.
Here, we can write f(n) as a recursive function, or a function that calls itself, since in the f(n) expression, we have another f function involved.
The same type of recursion applies to computer science algorithms as well.
For your reference, below is the code to sum the natural numbers from 1 to any given number n.