Making Recursive Functions Tail Recursive

First of this blog post assumes that you already have a basic understanding of recursion. I’ll use some Python for the code examples simply because it’s a popular language for learners, the concepts I’ll be talking about are language agnostic. In fact your preferred language might benefit more from tail recursion than Python. A look at a recursive factorial function Let’s first look at an issue with recursion, so that we can later fix it using tail recursion. [Read More]

What is recursion?

Recursion is a specific way to solve problems. It’s a pretty simple concept once you understand it, but regularly confuses people when they first learn it. In essence, when solving a problem, there often is a case that is simple to solve, a so-called base case. But many other cases that are complex and require a lot more computation. In recursion we make use of this. We look at the input, if we happen to have the simple case, we can go and return the easy solution. [Read More]

Don't exaggerate recursion overhead

A small pet peeve of mine is when people use the very na├»ve recursive implementation of the Fibonacci algorithm to show the overhead of recursion. Yes, recursion can have an overhead (depending on your environment), but it’s not nearly as much as you make it seem. The problem, The iterative version of the Fibonacci algorithm: def iterative_fibonacci(n): a, b = 0, 1 for _ in range(n): a, b = b, a + b return a has O(n) time complexity. [Read More]