Summary (Notes)

• Frequently, we will notice that a problem can be decomposed into a smaller version of itself.
• While this reasoning feels circular, we can still adapt of this form of decomposition to a computer program by using recursion.
• A recursive function is simply a function that calls itself.
• The following code snippet is an infinite loop—the function calls itself indefinitely!

def foo(x):
    foo(x)    # It never ends!

• To get around this, we must introduce a conditional that will stop the recursion at some pre-defined point:

def print_numbers(n):
    if n <= 0:
        print 'Done!'
    else:
        print n
        print_numbers(n - 1)

• With this, we can give a general skeleton for how a recursive function ought to be structured:

if <base case condition>:
    <do the base case>
else:
    <do the recursive case:
        perform computation at this step
        recursively call function>

• The base case of the recursive function is what we do with the smallest possible sub-problem we can solve. Frequently the base case is the simplest case of the problem to solve. This is determined by one or more of the parameters of the function. For example, we might designate the parameter n as the number of levels of draw of a recursive drawing; when n = 0, there are no levels left to draw so we don’t need to do anything!
• The recursive case can be broken up into two parts:
  1. Perform a minimal amount of work at this recursive step.
  2. Call the function recursively to perform the rest of the work.

Print Halves

Write a recursive function print_halves(n) that prints out n then n/2 then n/4 and so forth until the result is less than or equal to 1 (in ascending order). Here is some sample output from the function:

>>> print_halves(742)
1
2
5
11
23
46
92
185
371
742
>>> print_halves(1)
1
>>> print_halves(61)
1
3
7
15
30
61

Even Digits

Write a recursive function print_even_digits_from_right(n) that accepts an integer parameter and returns the number of even digits found in it, one per line starting with the right-most one. For example,

>>> print even_digits_from_right(8172)
2
8
>>> print even_digits_from_right(291875614)
4
6
8
2

Write a second function print_even_digits_from_left(n) that acts like print_even_digits_from_right but prints even digits starting from the left.

>>> print even_digits_from_left(8172)
8
2
>>> print even_digits_from_left(291875614)
2
8
6
4

When n is 0, you should return. You may assume that the user passes in a positive integer. And as a hint, remember that modulo can be used to both extract digits and test for evenness. Division can be used to slice off part of a number.

Print Sequence

Write a recursive function print_sequence(n) that prints a symmetric sequence of numbers composed of descending integers that end in 1, followed by a sequence of ascending integers that begin with 1. Here is the output of print_sequence for n from 1 to 10.

n = 1:  1
n = 2:  1 1
n = 3:  2 1 2
n = 4:  2 1 1 2
n = 5:  3 2 1 2 3
n = 6:  3 2 1 1 2 3
n = 7:  4 3 2 1 2 3 4
n = 8:  4 3 2 1 1 2 3 4
n = 9:  5 4 3 2 1 2 3 4 5
n = 10: 5 4 3 2 1 1 2 3 4 5

(Each line above is one invocation of the function. The n = xx: portion of the line is not part of the output.)

Note the pattern differs if n is odd or even. You may assume that the user passes in a value of n greater than or equal to one.

To write this function, you need to be able to print without injecting a newline. To do this, import the print_function from the __future__ module. print then becomes a normal function, rather than a statement which takes an optional named argument called end that specifies the character injected into the end of the string.

from __future__ import print_function

print('hello ', end='')     # end is the empty string so a newline is not added
print('world')              # a newline is still added by default if end is not provided

Sierpinski Triangle

If recursion had a motto, it would definitely be do more with less. And this is no more evident than with recursive graphics. For this final exercise, we will render the Sierpinski Triangle which is an example of a Fractal Pattern. A fractal is technically an infinite pattern, so our program will approximate it by only rendering the fractal up to a given recursion depth.

Write a function sierpinski(n) that renders a Sierpinski Triangle to a given recursion depth n similar to the examples above. At n = 0 the Sierpinski Triangle is just an equilateral triangle. At n > 0 the Sierpinski Triangle is made up of three smaller Sierpinski Triangles.

The helper function that you write that is recursive sierpinski_helper function could take three coordinate pairs as well as a recursive depth and renders a Sierpinski Triangle whose three points correspond to the three coordinate pairs with the given depth. The color of the Sierpinski Triangle does not have to be gold as in the above examples. Feel free to customize your Triangle to use whatever color(s) you’d like.

As a starting point, you should use the recursive function template that we outlined today. What is the base case of rendering the Triangle? What is the recursive case and how does it make its recursive calls?