--Originally published at Coding The Future
Hello my fellow programmers! I'm back again with a new and interesting topic for today. And I know, I said I would stop with the song references, but I just can't!
Today, I'm quoting Britney and her masterpiece Oops! I did it again to get us started on the topic of recursion. Recursion is the repetition of an algorithm for as many times as necessary to generate a conclusion.
What is recursion?
Recursion is funny because it's kind of related to infinity. Is not the same as loop, because the function "calls itself more than one time within its own body"1, becoming something like a function inside a function, inside a function, inside a function, and so on. It can also be interpreted as solving a big problem in smaller and smaller portions, and solving the first and smallest, followed by the second, until reaching the final big problem. However, a recursive function must end at some point to successfully obtain an answer.
Let's dive deeper into the topic. To do that, we will explore a popular example.
Examples of recursion
The Fibonacci numbers are the numbers of the following sequence of integer values:
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...
The Fibonacci numbers are defined by:
Fn = Fn-1 + Fn-2 with F0 = 0 and F1 = 1.
If we wanted to write a function that returns a determined index of the of Fibonacci series we would use something like this:
def fibo(n):
if n == 0:
return 0
elif n == 1:
return 1
else:
return fibo(n-1) + fibo(n-2)
As you may notice, the else statement, which exits within fibo calls itself again, until the the if or the elif are reached. If printed step by step, we would see how the function works backwards until it reaches 1, and then it works its way up. This is a clear example of recursion.
A more detailed explanation is available at PythonCourse.
In conclusion, recursion is used when one must go back to the "first known index" and work all the way up to return the index the user expects to see.
That's all for today! See y'all next time. ?
@emamex98
