Recursion

Many problems in computer science can be solved by repeatedly breaking down a problem into a slightly smaller problem, since once you know the solution to the smaller problem, it's easier to solve the original problem.

In the previous course, we learned about how to use recursion to solve such problems. We saw that recursion is a natural and elegant way to write algorithms that operate on data structures such as arrays, linked lists, and trees.

Watch the video below to remind yourself about how to think recursively and write a recursive function:

Recursion on data structures

Let's now take a look at the length() function, which uses recursion to find the length of a linked list:

class LinkedList:
    class Node:
        def __init__(self, val, next):
            self.val = val
            self.next = next

    def __length(self, head):
        if head is None:
            return None

        length_of_rest = self.length(head.next)
        return length_of_rest + 1

    def length(self):
        return self.__length(self.head)

This is the style in which we had been writing recursive functions. Notice a few things in particular:

• We have a recursive helper method, which uses a parameter head to track where we currently are in the list.
• We have a base case to check whether head is None; if it is, we have reached the end of the list.
• We make a recursive call, passing in head.next to advance to the next node in the list. We store the return value in a variable length_of_rest.
• Once we know the length of the rest of the list we simply need to add one and return the result.