Understanding recursion

Recursion is a process of internal, nested repetition. A well-known example of recursion are fractals, for example, the Sierpiński carpet – shapes repeat themselves while you keep zooming in. In the context of programming, recursion represents an ability of the function to call itself from its body. In some cases, this makes your code shorter and more expressive, as you can split complex problems into sets (Russian dolls?) of simple ones.

Consider an example of a factorial function (N! in math). A factorial of a value is a multiplicative of all numbers from 1 to the given one – for example, for 3, it will be 6: 1 * 2 * 3. The following is one way to compute a factorial through recursion:

def factorial(n):
    if n == 1:
        return n

    return n * factorial(n-1)

Here, the factorial of 1 will always return 1. For any other positive N, the function will return N, multiplied by the factorial of (N-1).

Because of recursion, this will happen again and again – the function will keep calling itself on a smaller value until the sequence reaches 1. From that moment, it will start returning the values, multiplying, returning again – going all the way back up the stack. Finally, it will return the value we're looking for. For us, though, the entire process will appear fast and simple:

>>> factorial(4)
24

The factorial of 4 is 24 = 1*2*3*4.

In the preceding function, we used the if statement for the first time. We will look at all types of statements in Chapter 4, Data Structures. Here, the statement checks whether the test value is true – in this case, if n is equal to 1, and, if yes, executes all the indented code. As return exits the function, none of the following code will be executed in this case. As you can see, indentations are also used here as well, and can be nested.

Another (more real-live) case for recursion is traversing over a complex structure. Take, for example, a website. If we need to collect all (or some) data from the site, we'll have to go to the main page, collect the info here, collect a number of links, and then start going over those links, and so on.

For an arbitrary website, we don't know the links and the overall number of pages. So, this is a good place to use recursion. We can run a data collection function on the main page. This function can then find the links, and, for each link, call itself. In their turns, those instances of the function will call more and more functions. While the overall process could be long and complicated, the code, in this case, will be short – and we won't need to know or even store the links in the process!

Table of Contents for Understanding recursion

Create new playlist

Sign In

Sign Up

Table of Contents for
Understanding recursion