“Of all ideas I have introduced to children, recursion stands out as the one idea that is particularly able to evoke an excited response.” — Seymour Papert, Mindstorms
You may not know it, but our life fundamentally is a recursive process. You are born into this world by your parents, you do the same for your baby, and your baby introduces the new life as well. Our DNA molecules also have a recursive structure, building on each other and uniting into the whole. Music composition is an inherently recursive process, too, where musical notes create a unique musical structure.
But there’s more.
Recursion is one of the most impactful principles in computer science and a BFF for coders and data scientists alike. Why? First of all, a lion’s share of sort and search algorithms are recursive. Secondly, you can hardly nail any interview without an established vision of this principle. All this makes recursion a staple in your programming playbook.
Today, we’ll get grounded into the basics of recursive programming skills in Python and go over some manifestations of this concept at play.
What Is Python Recursion?
Typically, people and fresh programmers struggle with understanding recursion for some reason. Sometimes, it’s the lack of mathematical background, other times, it’s their previous experience with languages that do not reflect recursive processes like JS or C.
But without understanding what you’re struggling with it’s hard to look into the magic of recursion. In simple words, recursion is a function that calls itself directly or indirectly.
Although it may seem unusual for a function to call itself, recursion can be helpful for solving lots of programming problems such as tree-like data structures.
On the flip side, recursion isn’t a one size fits all solution. There are quite a few downsides you need to take into account:
• Recursion is not the most popular option, since it makes the code less readable and verbose.
• Recursive implementations aren’t suitable for low resources, since they have a cost in stack space which leads to much more limited resources
• Sometimes, recursions may cause a slower execution time.
Get Started With Recursions
First of all, recursion must have a boundary or limit, i.e. the instance when the function stops calling itself, since boundaries prevent looping.
If we had not limited the cycle to 10, it would execute over and over again. Now let's try to stretch our limit.
Getting an error message, since there is a maximum recursion depth.
But it’s not a big deal, because we can easily extend the limit.
It’s obvious that if the function called on itself forever, we’d never get the result which means there wouldn’t be any point in implementing that function.
Let's make it more practical by taking Fibonacci numbers as an example. Those are a series of numbers when each successive one is equal to the sum of the previous two numbers. 1, 1, 2, 3, 5, 8, 13, ...
Let’s assume that n = 4. In this case, we’ll have a recursive call to fibonacci(3) and fibonacci(2). The second one will return 1, while the first one will result in two more function calls, i.e. fibonacci(2) and fibonacci(1).
Both calls return one, so the total is two. Thus, calling fibonacci(3) returns number 2, which is added to number 1 from calling fibonacci(2). The result of 3 is returned to the main branch of the program. The fourth element of the Fibonacci series equals three: 1 1 2 3.
To optimize this kind of algorithm, we can turn to the method of memoization. The latter refers to the programming practice when you store the results of expensive function calls and reuse them when the same inputs occur again.
To measure the execution time, you can use %timeit, which is an ipython magic function. It can be used to time a particular code piece (a single execution statement or a method).
Finding The Factorial In Python
The following example leverages the mathematical concept of the factorial. The factorial of a positive integer n, denoted as n !, is defined as follows: Therefore, n ! can be defined as the product of all integers from 1 to n, inclusive. The factorial is so recursively definable that programming texts almost always feature it as one of the textbook examples. You can express the definition of n ! recursively in the following way: Understanding The Factorial Recursively As we can see above, there are basic cases that can be solved without recursion. The more complex cases are reductive, which means that they are reducible to one of the base cases. The base cases ( n = 0 or n = 1) can be handled without recursion. For values of n greater than 1, n ! is defined in terms of ( n - 1) !, so the recursive solution progressively approaches the base case.
Thinking Recursively
Recursion is an ever-present concept in our daily lives with recursive solutions being fundamental for any programming language. As you can see, there are certain algorithms that just beg for a recursive solution. And once you apply the solution, you get a concise and idiomatic result.
Therefore, if you’re still bamboozled by writing a recursive tree traversal or sort algorithm, you might be missing an important milestone in your programming journey.