by Pau Pavón
It has many applications in mathematics and even trading (yes, you read that right: trading), but that’s not the point of this article. My goal today is to show you how you can compute any term of this series of numbers in five different programming languages using recursive functions.
I want to note that this isn’t the best method to do it — in fact, it could be considered the most basic method for this purpose. This is because the computing power required to calculate larger terms of the series is immense. The number of times the function is called causes a stack overflow in most languages.
Let’s analyze the function for a moment. If it gets 0 as an input, it returns 0. If it gets 1, it returns 1. If it gets 2… Well, in that case it falls into the else statement, which will call the function again for terms 2–1 (1) and 2–2 (0). That will return 1 and 0, and the two results will be added, returning 1. Perfect.
Now you can see why recursive funcions are a problem in some cases. Imagine you wanted the 100th term of the sequence. The function would call itself for the 99th and the 98th, which would themselves call the function again for the 98th and 97th, and 97th and 96th terms…and so on. It would be really slow.
And that’s it. I chose these languages just based on popularity — or at least because these 5 are the most common ones that I use They’re in no particular order. They could be classified by syntax difficulty, in my opinion, from Python (easiest) to C++ (hardest). But that depends on your personal opinion and your experience with each language.