lab03-practice : Recursion step-by-step (optional walkthrough)

num ready? description assigned due
lab03-practice ready Recursion step-by-step (optional walkthrough) Mon 04/22 11:59PM Tue 04/30 11:59PM

Learning Goals

In this lab, you’ll practice:

Before you get started, make sure to read up on recursion, specifically Chapter 4.2.

Open the lab side-by-side with your code window, so that you don’t need to scroll up and down to follow the instructions. Carefully read through the instructions top to bottom first, and then attempt to solve the function on your own, referring to the instructions when necessary.

In this lab, you will:

Table of Contents

  1. Instructions
  2. Questions to ask when solving recursion
  3. Recursion walk-through
    1. Sample problem
    2. Base case
    3. Recursive case
  4. Printing to Visualize Recursion!

Instructions

This lab contains a fully worked-out solution to a recursive function. Carefully read through the instructions top to bottom first, and then attempt to solve the function on your own, referring to the instructions when necessary.

Questions to ask when solving recursion

When designing a recursive solution, we need to answer the following questions:

Remember, a skeleton of the recursive function will have the following approximate structure:

# Note, this is just a pseudocode skeleton structure
def recF(val):
   if val == ...
      print/return fixedValue # base case / cases
   else / elif
      print/return recF(val_modified) 

# `val_modified` is a modified version of `val` that gets closer to the base case

Recursion walk-through

Sample problem

Write a function reverse_digits(), such that given an integer num (0 or greater), it reverses its digits using recursion, and returns a string that contains the reversed number. The function shouldn’t do anything if num < 0 (returns None).

For example, imagine you are given an integer num = 9321 as an input, so when the function reverses its digits, it should return the reversed digits as a string "1239".

Base case

Remember, a recursive function should always either print or return the result, depending on what you are asked to do. Every case (branch) has to have a print or a return, depending on the instructions.

In the sample problem above, the function takes an integer, which represents a number that needs to be reversed.

When writing a recursive function, you need to first identify the base case (or cases): the simplest case for which the function still works but does not need to do/compute/process anything. This case stops the recursion.

The simplest input value, which is the base case in this scenario, would be a single-digit num, since there is nothing to reverse.

The function needs to return the result as a string.

In your function, you can simply return the string consisting of the provided num, if num is between 0 and 9 (i.e., nothing to reverse).

def reverse_digits(num):
    """
    Reverse the digits of an integer (0 or greater), using recursion.
    Return a string that contains the reversed number.
    Returns None if num < 0.
    """
    if 0 <= num <= 9:
        return str(num)

Yay! We’re done with the base case.

Side note: you could’ve found other ways to implement the base case. For example, if len(num) == 1, is an alternative way to detect that we are looking at the “simplest input” where we have nothing to reverse.

Recursive case

The recursive case should always involve calling the function itself on the input that gets you closer to the base case.

Now, you can start developing an algorithm for a recursive solution.

After a single-digit number, the next simplest input would be a two-digit number. We can get from a two-digit number to a single digit by getting either the first or the second/last digit, which is a single-digit number that we need for the base case.

As we determined in Step 3, to get a single digit, we can get either the first or the second/last digit of the number.

You will need to decide if you are going to be reversing the number by going front-to-back or back-to-front (that is starting from the first digit and moving towards the last digit or starting from the last digit and moving towards the first digit).

For this example, let’s use the fact that the modulo operator % is going to give us the remainder of the division by 10 - this gets us the last digit. In this case, this is how you can change/reduce the provided input to get from the first recursive case to the base case: the “rest of the number” that is before the last digit, in this case is the input that will trigger the base case, because it is going to be a single digit.

What does it look like?

As you can see, in this step, we usually always figure out how the provided input needs to be divided/split/sliced/reduced, so that we can call the function to immediately trigger the base case.

Now that we have the “last digit” and processed the “rest of the number”, what do we need to do to reverse them?

What action do you need to take once you get the result from the base case in order to obtain the next simplest case?

You need to decide if you are going to be assembling the reversed digits at the end or at the beginning of the string that contains the base case.

Since we’ll be processing the number from the last digit, we’ll be assembling the rest of the digits after the “last digit” that will be placed at the beginning of the resulting reversed string.

What does it look like?

Let’s see if/how this would work for a longer number.

Looks like this might work!

The only part we are missing in the above pseudocode, is the “Give the rest of the number” part. How would you get 16 from 162? Well, if we got 2 by getting the remainder, we can get 16 by getting the integer part of dividing 162 by 10. We can express it using int(num/10) or simply as num//10.

We are ready to put it together. See if you can assemble the solution yourself.

def reverse_digits( num ):
    """
    Reverse the digits of an integer (0 or greater), using recursion.
    Return a string that contains the reversed number.
    Returns None if num < 0.
    """
    if 0 <= num <= 9:
        return str(num)

    elif num > 0:  # why is this not else? because "else" would work for -1 as well, which we don't want
        last = str(num%10)
        rest = reverse_digits(num//10)
        return last + rest

Because we correctly figured out the action that we need to take to get from the first recursive case to the base case, this recursive step should now work for arbitrarily large numbers.

At this point, all unit tests in this assignment should be passing, since the function is supposed to be returning the correct values.

Printing to Visualize Recursion!

Printing is a useful tool that will allow us to see what is happening during each step of the recursion. Let’s slightly modify the program to allow us to have readable print statements (using a technique described in zyBooks section Debugging Recursion). This way, we can really see what is happening during our recursive calls.

Let’s add an additional parameter to our function definition to let us print an indent on each successful recursive call.

def reverse_digits( num , indent='' )

Now let’s modify the recursive call! Just as we make our parameters move closer to the base case, let’s add an indentation for every successive recursive call we do.

def reverse_digits( num , indent='' ):
    """
    Reverse the digits of an integer (0 or greater), using recursion.
    Return a string that contains the reversed number.
    Returns None if num < 0.
    """
    if 0 <= num <= 9:
        return str(num)

    elif num > 0:
        last = str(num%10)
        rest = reverse_digits(num//10, indent + '|   ')
        return last + rest

We have added a way to see how deep our recursion goes, so now let’s add some informative print statements! These print statements throughout the function will let us know what is going on each step of the way.

def reverse_digits( num , indent='' ):
    """
    Reverse the digits of an integer (0 or greater), using recursion.
    Return a string that contains the reversed number.
    Returns None if num < 0.
    """

    print(f'{indent}Running reverse_digits({...})') # TODO: what is the input to the function?

    if 0 <= num <= 9:
        print(f'{indent}Base Case! Returning {...}') # TODO: what is returned?
        return str(num) 

    elif num > 0:
        print(f'{indent}The last digit is num%10: {...}') # TODO: add the computation
        print(f'{indent}"{num%10}" + reverse_digits({...})')

        last = str(num%10)
        ... = reverse_digits(..., indent + '|   ')   ## here is our recursive call

        print(f'{indent}"{...}" + "{...}"') # TODO: what is supposed to be concatenated?
        print(f'{indent}reverse_digits({...}) returned "{last + ...}"') # TODO: what was the input?

        return ...

If we were to call our function as reverse_digits(345), we should get the following output:

Running reverse_digits(345)
The last digit is num%10: 5
"5" + reverse_digits(34)
|   Running reverse_digits(34)
|   The last digit is num%10: 4
|   "4" + reverse_digits(3)
|   |   Running reverse_digits(3)
|   |   Base Case! Returning 3
|   "4" + "3"
|   reverse_digits(34) returned "43"
"5" + "43"
reverse_digits(345) returned "543"

Great! Now we will be able to have a visual representation of what is going on with our recursion. Notice how with each recursive call, indent gets increased. So the deeper our recursion goes, the further indented the print statements will be.