Recursion

What is Recursion?

Recursion is a simple yet powerful programming concept which involves functions calling itself. In most cases, you might make a function call itself to get what it returns under a specific test case. Many programming problems will involve recursion to traverse sub-objects or search a tree or graph.

Recursion Example

The most popular form and example of using recursion in programming is calculating fibonacci sequence terms. Here's some example code:

def fib(n):
    if n <= 2:
        return 1
    else:
        return fib(n - 1) + fib(n - 2)
    

This fibonacci example is pretty self-explanatory. We first create a function fib which takes one parameter - the position of the term we want.

After, we first do a simple if-statement check. If n is less than 2, we will return 1 as the value of the term. Otherwise, we follow the simple rules of the fibonacci sequence and attempt to return the sum of the two previous terms, or fib(n - 1) + fib(n - 2).

However, do note that this is one of the more less efficient algorithms for recursion, because our program can easily exceed the maximum recursion limit, which is 1000. So, if you were to call fib(1001), then you would hit an error.

However, in the next tutorial on Caching, we'll learn how to make our code more efficent.

Recursion Programming Problems and Exercises

Here are some fun programming problems for practicing Recursion skills:

• Fractals
• Bananas
• Unfriend
• A Recursion Problem