Lecture 22: Introduction to Recursion

Acknowledgment. This notebook has been adapted from Wellesley CS111 course materials: (http://cs111.wellesley.edu/spring19).

First recursion: countDown

Notice the repeated printing, despite the lack of an explicit for or while loop in the body of the function.

In [1]:
def countDown(n):
    '''Prints numbers from n down to 1''' 
    if n < 1:  # Base case
        pass  # Do nothing
    else: # Recursive case: n >= 1: 
        print(n)
        countDown(n-1)
In [2]:
countDown(5)

5
4
3
2
1
In [3]:
countDown(-5)
In [4]:
countDown(10)

10
9
8
7
6
5
4
3
2
1

Side-note: simplifying the code by changing the base case

If the base case does nothing, we can re-write the conditional.

This is a general fact about if-statements, not necessarily related to recursion.

In [5]:
def countDown(n):
    '''Prints numbers from n down to 1''' 
    if n > 0:
        print(n)
        countDown(n-1)
In [6]:
countDown(6)

6
5
4
3
2
1

Gotcha-s in Recursion

Gotcha #1: Subproblem in not getting smaller

Below is an example of a common mistake when using recursion.

Can you figure out what is wrong in the code without running it?

In [ ]:
def countDownGotcha(n):
    '''Prints numbers from n down to 1''' 
    if n <= 0:  # Base case
        pass  # Do nothing
    else: # Recursive case: n>0: 
        print(n)
        countDownGotcha(n)
In [ ]:
countDownGotcha(10)

If you run the line above, you should see toward the end of the output, the dreaded error:

RuntimeError: maximum recursion depth exceeded while calling a Python object

It means that the memory allocated to your program doesn't have space anymore for all the opened execution frames that are opened while your function is recursively invoking itself, endlessly!

Restart the kernel if you ran this code and got the error.

Gotcha #2: Missing/Unreachable the base case

The following example will also lead to infinite recursion. Can you explain why?
How can you fix the problem?

In [ ]:
def printHalvesGotcha(n): 
   """Prints n, n/2, down to ... 1"""
   if n >= 1:
        print(n)
        printHalvesGotcha(n/2)
In [ ]:
printHalvesGotcha(10)

Recursive countUp

Define a recursive function countUp that counts up from 1 to n rather than n to 1. countUp(5) should print:

1  
2  
3  
4  
5
In [7]:
def countUp(n):
    '''Prints out integers from 1 up to n'''
    if n < 1:
        pass # do nothing
    else:
        countUp(n-1)
        print(n)
In [8]:
countUp(5)

1
2
3
4
5
In [9]:
countUp(-5)

countDownUp

How about a recursive function that counts down and up? This one is a bit more complex, but very elegant.

In [10]:
def countDownUp(n):
    """Prints integers from n down to 1
    and then from 1 up to n."""
    if n < 1:
        pass # do nothing
    else:
        print(n)
        countDownUp(n-1)
        print(n)
In [11]:
countDownUp(4)

4
3
2
1
1
2
3
4
In [12]:
countDownUp(10)

10
9
8
7
6
5
4
3
2
1
1
2
3
4
5
6
7
8
9
10

Recursive Pattern: triangle

Lets create some recursive patterns.

Write a recursive function called triangle that takes a length parameter n and a character c and draws a triangle pattern composed of lines of c, starting with length len going down to 1.

For example: triangle(10, '*') should print: **********
*********
********
*******
******
*****
****
***
**
*

In [13]:
def triangle(n, c):
    if n < 1:
        pass # do nothing
    else:
        print( n * c)
        triangle(n-1, c)
In [14]:
triangle(10, '*')

**********
*********
********
*******
******
*****
****
***
**
*
In [15]:
triangle(6, '^')

^^^^^^
^^^^^
^^^^
^^^
^^
^

Recursive Pattern: triangleAlt

Write a recursive function called triangleAlt that takes a length parameter n and two characters c1 and c2 and draws a triangle pattern similar to the previous example but now the rows must alternate between c1 and c2 (starting with char1).

For example: triangleAlt(8, '@', '#') should print: @@@@@@@@
#######
@@@@@@
#####
@@@@
###
@@
#

In [16]:
def triangleAlt(n, c1, c2):
    if n < 1:
        pass # do nothing
    else:
        print(n * c1)
        triangleAlt(n-1, c2, c1)
In [17]:
triangleAlt(10, '@', '#')

@@@@@@@@@@
#########
@@@@@@@@
#######
@@@@@@
#####
@@@@
###
@@
#
In [18]:
triangleAlt(9, 'a', 'b')

aaaaaaaaa
bbbbbbbb
aaaaaaa
bbbbbb
aaaaa
bbbb
aaa
bb
a

Excercise: triangleDownUp

Write a recursive function called triangleDownUp that takes a length parameter n and two characters c1 and c2 and draws a triangle of rows of characters getting smaller starting with length n down to 1 and then should print the same triangle "inverted."

For example: triangleDownUp(8, '@', '#') should print:
@@@@@@@@
#######
@@@@@@
#####
@@@@
###
@@
#
#
@@
###
@@@@
#####
@@@@@@
#######
@@@@@@@@

In [2]:
def triangleDownUp(n, c1, c2):
    if n < 1:
        pass
    else:
        print(n * c1)
        triangleDownUp(n-1, c2, c1)
        print(n * c1)
In [3]:
triangleDownUp(8, '@', '#')

@@@@@@@@
#######
@@@@@@
#####
@@@@
###
@@
#
#
@@
###
@@@@
#####
@@@@@@
#######
@@@@@@@@