Writing a recursive function in Python

Question

Assume the availability of a function named printStars that can be passed a parameter containing a non-negative integer value. The function prints out the given number of asterisks.

Write a function named printTriangle that receives a parameter that holds a non-negative integer value and prints a triangle of asterisks as follows: first a line of n asterisks, followed by a line of n-1 askterisks, and then a line of n-2 asterisks, and so on.

For example, if the function received 5, it would print

*****
****
***
**
*

The function must not use a loop of any kind (for, while, do-while) to accomplish its job. The function should invoke printStars to accom;lish the task of printing a single line.

I have the base case worked out I believe. Here is my code:

def printTriangle(n):
    if n == 1:
        printStars(n)

I need some help figuring out the recursive step. I am thinking it uses n-1 as a parameter, but I am not sure how to call the printTriangle function properly. Thanks in advance.

Answer 1

Recursion works by reducing a problem instance characterised by n to one characterised by n-1. To be finite it has to stop at some instance n0.

For this problem n is the length of the string.

• So when implementing f if you have some function that can handle to print the wanted string of length n-1, you will just print one asterisk and then call that function. The trick is that this function is the function f itself. For a string of length 0 you print nothing and return.

This will yield a recursive function f that prints a string of n asterisks when called as f(n).

Next you handle the triangle by providing some function g.

• It will return and do nothing if it is called with argument 0. Else it will use f(n) to print one row, then print the line feed and then call itself with argument n-1.

A call of g(5) should print the example triangle.

You should use the longer names from your question text for the functions.

Answer 2

Let's use n=5 as an example. A 5-row triangle

*****    # 5 stars ...
****     # ...followed by a 4-row triangle
***
**
*

is just a row of 5 stars, printable with printStars(5), followed by a 4-row triangle, printable with printTriangle(4). Similarly, the 4-row triangle is just a row of 4 stars followed by a 3-row triangle. In general, an n-row triangle is just a row of n stars, followed by an n-1-row triangle. As an old college professor used to tell us, "Trust your recursion", by which he meant, while writing printTriangle, assume that printTriangle will work correctly and use it when you can. You print an n-row triangle by printing a row of n stars with printStars(n), followed by an n-1-row triangle with printTriangle(n-1). This means that the base case is even simpler: for n=0, do nothing! Otherwise, print a row of n stars and then recurse on the smaller triangle that follows.

def printTriangle(n):
    if n == 0:
        # Base case
        return
    else:
        # Recursive case
        printStars(n)
        printTriangle(n-1)

Answer 3

Print n stars, reduce n by 1, repeat until n = 0

def printTriangle(n):
    if n > 0:
        printStars(n)
        printTriangle(n-1)

This function keeps calling itself until n is 0

Answer 4

def printTriangle(n):
  if n > 0:
    printStars(n)
    printTriangle(n-1)

Answer 5

The function prints n stars, then decrements by calling itself with the parameter n - 1. So the base case should be when n is equal to 1 because it's illogical to decrement it any further. Decrements only happens when n is greater than 1.

So in pseudocode it comes out to:

function pstars(n)
    printStars(n)

    if (n > 1)
        pstars(n - 1)

See how it calls itself and decrements n?

Spoilers in Python code:

def printTriangle(n): printStars(n) if n > 1: printTriangle(n - 1)

Answer 6

Add in a print statement, or some equivalent, to make each recursive step print to a new line.

def printTriangle(n):
    if n == 0:
        return
    if n > 0:
        printStars(n)
        print()
        printTriangle(n-1)