Understanding a Recursive Problem

Understanding the Problem

In the previous lessons, we learned the basic concept of recursion, what it is and when it can be used. Now, we will discuss how recursion works.

Let’s have a look at an example code:

On first glance, we notice that the targetNumber is decreased by $5$ and then again printPattern() is being called. However, there are two print() statements preceding and succeeding the recursive call.

Code Explanation

We want to print a pattern: $10$ $5$ $0$ $5$ $10$. Notice, we first decrease the targetNumber by $5$ then increase the targetNumber by $5$. However, the middle number is printed only once, i.e., $0$ is printed once.

Hence, this becomes our base case:

if targetNumber <= 0:
  print targetNumber
  return

Now, for the rest of the numbers, we print them twice, i.e., on each side of the base case.

print targetNumber
printPattern(targetNumber - 5)
print targetNumber

This is our recursive case.

There are three methods commonly used to understand the code flow of a recursive program and to dry run code:

Visualizing Trough Stack

The concept of a stack is critical in recursion. When you start visualizing your function calls through a stack and how it returns when reaching a base case - the concept of recursive calls and its output becomes easier to comprehend.

We have already looked at this in the previous lesson, however, let’s revisit it, with this example:

Drawing a Recursive Tree

Recursive functions usually tend to act like a tree. The parent is the main function call and each recursive call that is made becomes a child node.

We will be using the recursive tree method for representing recursive function calls throughout our course.

Keeping a Track of your Variables

Keeping track of variables can help dry run codes that are very complicated. It is a detailed method and can be time-consuming. However, this method can be helpful while writing recursive functions. Because, as the function gets more complicated, it becomes harder to store everything in your head and keep a track of all the variables and function calls. Mainly because as we saw from the example above, we may have to perform various functions in between recursive calls.

In the next lesson, we have a quick quiz for you to test your understanding of this chapter.