--Originally published at Coding The Future
via GIPHY
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 Continue reading "OOPS! I DID IT AGAIN" →