Diamonds, butterflies and recursive triangles in Python

Why this matters

The diamond and the butterfly are the hardest shapes in this module, and the reason is not the loops. They ask you to put two shapes together, and to join them without printing a row twice. A diamond is a pyramid followed by an upside-down pyramid. A butterfly is a triangle mirrored across a vertical gap. In both cases the difficult part is the join: which row belongs to which half, and how many rows the second half needs.

These shapes are common in interviews because they test whether you can split one picture into two smaller pictures, and whether you can reuse code instead of copying it. They also introduce the last big idea of the module, a function that calls itself. That idea is called recursion, and it appears in many later topics, such as trees, sorting and searching. A diamond is a gentle first place to see it.

In this lesson you will print a diamond with a helper function, print a butterfly with a second helper, and then write short recursive functions that print triangles. You will also see what happens when a recursive function has no way to stop. The examples set the size n inside the code, so every program runs without typing anything. The module assignment at the end reads its input from the user.

The idea: two halves that share a middle

A diamond has seven rows when n is 4. Its top half is a pyramid with four rows: 1, 3, 5 and 7 stars. Its bottom half is an upside-down pyramid with three rows: 5, 3 and 1 stars. The widest row, with seven stars, sits in the middle and belongs to the top half only.

That last point is the whole trick. If both halves printed the widest row, the picture would have two full rows in the middle, and it would look flat. So the top half counts i from 1 up to n, and the bottom half counts i from n - 1 down to 1. The bottom half starts one row short, because the middle row is already printed.

Python's range function produces these counts. range(1, n + 1) gives the numbers from 1 up to n. The second number is never included, which is why the stop value is n + 1 and not n. range(n - 1, 0, -1) counts down from n - 1 to 1. The third number is the step, which is minus 1 here. The stop value 0 is never included. The rule for a beginner is short: the first number is included, the second is not, and the third is the step.

The table shows the rows for n equal to 4.

The rows are the centred pyramid from the pyramid lesson, followed by the same rows counted back down. Each row needs the same two counts as before, spaces and stars, and the formulas do not change. Only the order of the rows changes. You can reuse the pyramid code and decide only the order of the calls.

Count the rows in the table: 4 plus 3 is 7, which is 2 * n - 1, the total height of any diamond.

Worked example 1: a diamond with a helper function

The diamond program below uses a function called print_row. The function takes two numbers, the spaces and the stars, and prints one row. The main part of the program calls print_row seven times for n equal to 4, with the right numbers each time.

In Python, text can be multiplied by a whole number. "*" * 3 gives ***, and " " * 2 gives two spaces. The plus sign joins two pieces of text. So " " * spaces + "*" * stars builds one complete row in a single line. When spaces is 0, the first piece is an empty string, and the row starts with the stars.

The output for 4 is:

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

Read print_diamond first. It has two loops. The first loop runs i from 1 to 4 and prints the top half. The second loop runs i from 3 down to 1 and prints the bottom half. Look at the start of each loop. The first starts at i equal to 1, which includes the widest row at i equal to 4. The second starts at n - 1, which is 3, so it skips the widest row. That one number in the range call is what prevents the duplicate row.

Now read print_row. It takes spaces and stars as its two inputs, and it does not know about i or n. That independence is the point. The function only needs to know how many characters to print, and the caller works out the counts from the shape. You can test print_row on its own with any numbers, and you can change the shape by changing only print_diamond.

Trace the last call. The second loop has i equal to 1. The call is print_row(n - i, 2 * i - 1), which is print_row(3, 1). The function builds " " * 3 + "*" * 1, which is three spaces and one star, and prints it. That is the last line of the output, *.

Worked example 2: a butterfly

A butterfly is a shape with two wings. Each wing is a right triangle, one on the left edge and one on the right, and the two wings point at each other across a gap. The top half of a butterfly for n equal to 3 has three rows. Row 1 has one star, a gap, and one star. Row 2 has two stars, a smaller gap, and two stars. Row 3 has three stars on each side and no gap, so the middle is solid.

The counts for row i are simple. The left wing has i stars. The right wing has i stars. The gap in the middle has 2 * (n - i) spaces, which is zero in the widest row and grows as the rows get narrower. The bottom half repeats the top half in reverse, without the widest row, as in the diamond.

The table has five rows, with 2 * n - 1 rows in total, as in the diamond. The gap is the new count. It is four spaces in the outer rows, two in the middle, and zero in the widest row. Check the gap on row 1 with n equal to 3: 2 * (3 - 1) is 4, and the row is one star, four spaces and one star. That is six characters, which is the full width of the widest row, 2 * n characters.

This version of the helper returns the row as text instead of printing it. butterfly_row gives back one string, and print_butterfly decides what to do with it. A function that returns a value can be tested, because you can check the value. A function that only prints can be checked only by reading the screen.

The output for 3 is:

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

Check the picture against the table. Row 2 has two stars, two spaces and two stars, which is ** **. Row 3 has three stars on each side, and no gap, so it is ******. The bottom half mirrors the top half exactly, because the bottom loop runs i from 2 down to 1 and calls the same function.

Notice that the function takes i and n, not the counts. It computes the gap from them, so the caller does not need to know how the gap works. This is the same design idea as print_row in the diamond, but this helper carries more of the logic. Choose the design that keeps the caller simple. A helper function should answer one question: how do I build one row of this shape?

Worked example 3: a recursive triangle

Recursion is a function that calls itself. It sounds strange the first time, so look at a small example before you learn the rules. A recursive triangle prints a triangle of stars by saying: a triangle of size n is a triangle of size n - 1, followed by one more row of n stars. The triangle of size n - 1 is made the same way, and so on, until the size reaches zero. A triangle of size zero prints nothing, and that is the stopping point.

Each part of that sentence becomes code. The function takes a number n. If n is zero, it returns straight away, because there is nothing to print. Otherwise it calls itself with n - 1, which prints every row above the last one. Then it prints the row of n stars and returns. The call to itself is the step that makes the recursion work, and the check for zero is the rule that stops it.

The output for 4 is:

*
**
***
****

The order of the work is the key to this program. The row of stars is printed after the call triangle(n - 1) returns. So the smallest triangle prints first, at the top, and each larger call adds its row underneath. The row for n equal to 4 is printed last, at the bottom.

Follow the calls in order. The program first calls triangle(4), which calls triangle(3), then triangle(2), then triangle(1), then triangle(0). The call triangle(0) returns at once. Then triangle(1) prints one star and returns. Then triangle(2) prints two stars and returns, and so on. The stars are printed on the way back up, which is why the order is smallest first.

The stopping rule is if n == 0: return. Without it the calls would go on forever, with n equal to minus 1, minus 2, and so on. The base case is the simplest version of the problem, which needs no further work. Every recursive function needs a base case, and it must be reached after a finite number of calls. In this function, each call moves n one step closer to zero, so the base case is always reached for a positive n.

Worked example 4: a recursive inverted triangle

The inverted triangle can be written recursively too. Here the order of the work changes. The function prints its row of n stars first, and then calls itself with n - 1. So the widest row prints first, at the top, and the smaller triangles follow below it.

The only difference from the previous example is the position of the print and the call. Put the print before the call and the rows come out largest first. Put it after the call and they come out smallest first. This small change in order is an important skill, because many recursive algorithms do their work either before or after the recursive call, and the position decides the result.

The output for 4 is:

****
***
**
*

Trace the first two calls. inverted(4) checks n == 0, which is false, so it prints four stars. Then it calls inverted(3), which prints three stars and calls inverted(2). The calls continue until inverted(0), which returns at once. Nothing is printed by that call, so the output ends after the single star of inverted(1).

Compare the two recursive programs. They use the same base case and the same call, but the print is in a different place. Ask yourself, for any recursive function, whether the work must happen before the recursive call, after it, or on both sides. For a triangle that grows, the work happens after the call. For a triangle that shrinks, the work happens before the call. Getting the order right is most of the design.

Worked example 5: counting down with recursion

The recursive triangles printed stars. The same function can print numbers, and that is a useful way to see the order of work without the distraction of the picture. This program prints the numbers from n down to 1, one per line. The print comes before the recursive call, so the largest number prints first.

The output for 4 is:

4
3
2
1

Trace the calls. count_down(4) prints 4 and then calls count_down(3). That call prints 3 and calls count_down(2), which prints 2 and calls count_down(1). That call prints 1 and calls count_down(0). The last call checks n == 0, which is true, and returns without printing. Each earlier call then finishes too, but it has nothing left to do, so the program ends after the 1.

Now compare it with the recursive triangle from worked example 3. There the print came after the call, so the smallest triangle printed first. Here the print comes before the call, so the largest number prints first. The base case and the call have the same shape in both programs. Only the position of the print changed, and that single change set the order of the output. When you write a recursive function, decide where the work goes before you write anything else.

A recursive countdown is a common first exercise in interviews, because it shows whether you understand the base case, the recursive call and the order of work all at once. A strong answer names the base case, says what the call does, and then says where the print goes and why.

What happens inside a recursive call

Each call to a function creates a new frame, which is a small block of memory that holds the function's inputs and its local variables. A call to triangle(4) creates a frame with n equal to 4. That frame calls triangle(3), which creates a second frame with n equal to 3, and so on. The frames stack up in memory, one on top of the other. The stack of frames is the call stack. The top frame is the one that runs now, and it is the only one that makes progress.

When a call returns, its frame is removed from the top of the stack, and the frame below it continues from the line after its call. In the recursive triangle, the frame for triangle(3) is on the stack while triangle(2) runs. When triangle(2) returns, the frame for triangle(3) resumes, prints its row of three stars, and then returns to triangle(4). This is why the rows appear in reverse order of the calls.

Python limits how deep the call stack can grow. The limit is called the recursion limit. On the Python 3.14 version used to check this lesson, sys.getrecursionlimit() returns 1000. When a call would go past the limit, Python stops the program with an error called RecursionError. The limit protects the computer, because each frame uses real memory, and an unlimited stack could take all of it. You can raise the limit with sys.setrecursionlimit, but a very high value can crash the interpreter. The safer fix is a base case that every call reaches.

The program below is a function with no stopping rule. It calls itself forever.

def forever(depth):
    return forever(depth + 1)
 
 
forever(0)

When you run this program, Python prints a traceback, which is the list of calls that led to the error. The start and end of the real output are:

Traceback (most recent call last):
  File ".../main.py", line 5, in <module>
    forever(0)
    ~~~~~~~^^^
  File ".../main.py", line 2, in forever
    return forever(depth + 1)
  File ".../main.py", line 2, in forever
    return forever(depth + 1)
  File ".../main.py", line 2, in forever
    return forever(depth + 1)
  [Previous line repeated 996 more times]
RecursionError: maximum recursion depth exceeded

The last line names the error, which is RecursionError, and the message says the depth went past the limit. The lines above it show where the calls were made. Each one points at line 2, which is the recursive call. A long list of the same line, ended by [Previous line repeated 996 more times], is the sign of unbounded recursion. The ... in the path replaces the folder where the file was saved. The fix is to add a base case, and to check that every call moves the input toward the base case.

Designing the helper functions

Both the diamond and the butterfly use a helper function that builds or prints one row, and the choice of inputs matters. The diamond helper, print_row, takes spaces and stars, which are the two numbers a row needs. The caller works out those counts from the shape. The butterfly helper, butterfly_row, takes i and n, and it computes its own counts. Neither design is wrong, but they put the shape's formulas in different places.

Consider what each design does in practice. A helper that takes counts knows nothing about the shape. It can print any centred row, so it is easy to test with odd numbers, and it can be reused by a pyramid, a diamond or a different shape. The cost is that the caller must compute the counts correctly. If the caller passes a wrong count, the row is wrong, and the bug sits in the caller, far from the formula that caused it.

A helper that takes the row number and the size hides the formula inside itself. The caller is simpler, because it only says which row to build. The cost is that the helper is tied to one shape. The butterfly helper is a good example. Its gap formula, 2 * (n - i), is used nowhere else, so keeping it inside the helper keeps the shape's logic in one place.

Choose the design by asking where the formula will be read. If the formula is shared by several shapes, pass the counts. If the formula belongs to one shape, pass the row number and the size. Either way, name the helper after what it does, such as print_row or butterfly_row, and not after how it works. A reader who sees the name should know the output without reading the body.

A version that builds all the rows first and prints them at the end is often clearer. The function returns a list of strings, one string for each row. The join method then puts the rows together with line breaks between them. "\n".join(rows) gives one string with a line break between each pair of rows. Printing that string once is the same as printing each row, and it keeps the building and the printing apart.

The output for 4 is:

   *
  ***
 *****
*******
 *****
  ***
   *
rows: 7
stars: 25

The total is found by looping over the rows and asking each row how many times "*" appears. The count is taken from the finished rows, so it matches exactly what the program prints.

Python does not check the types of inputs when the program runs. A function can name its inputs with type hints, such as def print_row(spaces: int, stars: int) -> None:. The hints say what the function expects and what it returns, and an editor can warn you when a call does not match. They do not stop a wrong value at run time. The -> None part says the function returns nothing and only prints.

A helper does not need to be long. Four to eight lines is a common size for a row builder. If a helper grows past a screen, look for a second job inside it and move that job into its own function. Each function should answer one question, and the names should make the answers easy to find.

Common mistakes and their real messages

Mistake 1: a recursive call with no stopping rule. This is the mistake the last section showed. The function calls itself forever, and Python stops with RecursionError: maximum recursion depth exceeded. Add a base case, such as if n == 0: return, at the start of the function. Then check that every recursive call moves n closer to the base case.

Mistake 2: a recursive call that moves the wrong way. If the triangle function calls triangle(n + 1) instead of triangle(n - 1), the value never reaches zero. The result is the same error, even though the base case is correct. The traceback ends like this:

  File ".../main.py", line 4, in triangle
    triangle(n + 1)
    ~~~~~~~~^^^^^^^
  [Previous line repeated 996 more times]
RecursionError: maximum recursion depth exceeded

Read each recursive call and ask whether its input is closer to the base case than the current input.

Mistake 3: the print in the wrong place. In the recursive triangle, moving the print above the recursive call gives the inverted order. The output is a different shape, upside down. Decide where the work belongs before you write the call, and test with n equal to 2 or 3, where the order is easy to see.

Mistake 4: a diamond that prints the middle row twice. The bottom loop must start at n - 1, not at n. Starting it at n prints the widest row again, and the diamond looks flat in the middle. For n equal to 3 the wrong version prints this:

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

Check the start of the second loop against the table. For n equal to 4 the bottom half begins with one space and five stars, and the widest row is not in it.

Mistake 5: a butterfly gap with the wrong count. The gap is 2 * (n - i), not n - i. With the single formula the wings sit too close together, so every row above the widest one is too narrow. For n equal to 3 the wrong gap prints this:

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

Check row 1 on paper: for n equal to 3 the gap must be four spaces, which makes the row six characters wide.

Mistake 6: print ends every call with a line break. In Python, print adds a line break after its text by default. A loop that prints one star at a time puts each star on its own line. The fix is end="", which replaces the line break with nothing, followed by one plain print() at the end of the row. The next program shows both versions.

The output is:

*
*
*
---
***

The underscore in for _ in range(stars) is a name for a value that the loop does not use. It is a common convention in Python.

Each of these mistakes leaves a clear sign. A RecursionError names itself, and its traceback shows the same line repeated. A flat diamond shows the duplicate row in the middle. A butterfly with a narrow middle shows the wrong gap formula. An upside-down triangle shows the call and the print in the wrong order. A column of stars where a row should be shows a missing end="". Learn to read the sign, and you will know which line to check.

Debugging walkthrough: a recursive triangle prints upside down

Suppose you write the recursive triangle, but you put the print before the call. For an input of 3 the output is this:

***
**
*

You wanted the smallest row first. The picture has the widest row at the top, which is the output of the inverted function, not the triangle. Walk through the steps.

Step 1: compare the first printed row with the first row you want. The first row has three stars, but a triangle must start with one star.

Step 2: look at the order of the print and the recursive call in the function. If the print comes before triangle(n - 1), the largest row prints first. That is the cause.

Step 3: move the print after the recursive call, so the call finishes first and the print runs on the way back up. Run the program again. The first row now has one star.

Step 4: check the base case as well. For n equal to 0 the function returns at once, so nothing is printed for the empty triangle. Test with n equal to 1 and n equal to 2 to confirm each stage. With n equal to 2 the output should be one star and then two stars.

Another useful technique is to print a message at the start and the end of the function, with the value of n. Messages such as enter 2 and leave 2 show the order of the calls. The output for triangle(2) with these messages is:

enter 2
enter 1
enter 0
leave 0
*
leave 1
**
leave 2

Read it from the top. Each enter line is a call going down, and each leave line is a call coming back up. The stars appear between the leave lines of the smaller calls, which is the order the code promises. Remove the messages when the order is right. This is the same idea as the call stack, but written by hand, and it works well for any recursive function.

Variations and edge cases

For n equal to 1, the diamond is a single star. The butterfly is two stars with no gap, which forms one row, **. Check these first. A diamond with n equal to 1 has a bottom loop that runs over range(0, 0, -1). That range is empty, so only the top half prints. Python confirms this with list(range(0, 0, -1)), which gives [].

For n equal to 2, the diamond has three rows: one star, three stars, one star. The bottom loop runs once, for i equal to 1, and prints the row with one star. Its output is *, ***, *. For the butterfly with n equal to 2, the middle row is four stars, which is the widest row with no gap, and the picture is * *, ****, * *.

A hollow diamond is the natural next step. Use the border idea from the hollow lesson, with one test for each cell in each row. A cell in the diamond is a star when its distance from the centre is exactly n // 2. The distance here is the number of rows away plus the number of columns away. The exercises at the end ask you to write it.

The countdown and the count-up in the exercises differ only in where the print sits. That one choice reverses the order of the output, which is the same lesson the two triangles taught.

Finally, a recursive function uses memory for each call, so a deep recursion can fail even when its logic is right. For a triangle of 4 rows this is nothing. For a recursion that goes more than about a thousand levels deep, Python stops it with RecursionError, even when the base case is correct. A loop has no such limit, which is one reason to choose a loop when the depth is large and simple.

Interview questions and real uses

Diamonds and butterflies are common interview questions because they test the design, not just the loops. A strong answer to "print a diamond for n" says three things. It names the two halves and their row counts. It says why the widest row belongs to the top half only. And it shows the helper function that builds a row, so the main part of the program stays short. The interviewer wants to hear that you can split a picture into reusable pieces.

A typical follow-up asks you to count the stars in a diamond. For n equal to 4, the answer is 25. The top half has 1, 3, 5 and 7 stars, which sum to 16, and the bottom half has 5, 3 and 1 stars, which sum to 9. In general a diamond of size n has n * n + (n - 1) * (n - 1) stars. The check for n equal to 3 gives 9 plus 4, which is 13, and diamond_rows with n set to 3 prints stars: 13. Showing the formula, and checking it for two sizes, is a strong answer.

Recursion appears in many interview questions, and this module's triangles are an early example. The interviewer may ask you to write a recursive function, to say what its base case is, and to say what the call stack looks like. A clear answer names the base case first, then the recursive call, then the work before or after the call. Thinking in that order is the skill that carries over to trees and to sorting.

Shapes like these show up in real programs as text art, in console tools that draw a progress bar or a symmetric banner, and in test output for layout code. Each shape is a set of rows, and each row is a centred run of characters. The same idea of splitting a shape into a top and a bottom, and mirroring a half to make the other, appears when a program draws a symmetric icon or a bar chart that grows from the middle.

Practice

Try each exercise before you open its answer. Write the program, and check it on paper with a small n before you run it.

1. Print the diamond for n equal to 3. Predict the number of rows before you run the program. How many rows does a diamond of size n have?

Show the answer

The diamond has five rows, because 2 * 3 - 1 is 5. The output is *, ***, *****, ***, *. Use the print_diamond function from worked example 1 with n set to 3.

2. Predict the number of stars in the widest row of a diamond with n equal to 5, and the total number of stars in the whole diamond.

Show the answer

The widest row has nine stars, because 2 * 5 - 1 is 9. The total is 25 plus 16, which is 41. The stars are the sum of 1, 3, 5, 7, 9, 7, 5, 3 and 1. The formula n * n + (n - 1) * (n - 1) gives the same result: 25 + 16 = 41.

3. Print the butterfly for n equal to 2. Predict the middle row before you run the program.

Show the answer

The output is * *, then ****, then * *. The middle row has no gap, because 2 * (2 - 2) is 0, so it is four stars. Use the print_butterfly function from worked example 2 with n set to 2.

4. Predict the output of the recursive triangle when the input is 3, and explain why the rows are printed in that order.

Show the answer

The output is *, then **, then ***. The print runs after the recursive call returns, so the smallest triangle prints first, at the top, and each larger call adds its row below.

5. Write a recursive function count_up(n) that prints the numbers from 1 up to n, one per line. Put the print after the recursive call, and test it with n set to 4.

Show the answer

The function is:

def count_up(n):
    if n == 0:
        return
    count_up(n - 1)
    print(n)

For n equal to 4 the output is 1, 2, 3 and 4, one per line. The print is after the call, so the smallest number prints first.

6. Predict the output of this function when it is called with 3, and write your answer before you run it.

def twice(n):
    if n == 0:
        return
    print(n)
    twice(n - 1)
    print(n)

Show the answer

The output is 3, 2, 1, 1, 2 and 3, one per line. The first print runs on the way down, so 3, 2 and 1 appear in that order. The second print runs on the way back up, so 1, 2 and 3 follow. The base case prints nothing.

7. Find the bug. A program prints the recursive triangle, but the function has triangle(n + 1) as its recursive call. What happens, and why?

Show the answer

The value of n grows each time, so it never reaches the base case of zero. The calls go on until the call stack is full, and Python stops the program with RecursionError: maximum recursion depth exceeded. Change the call to triangle(n - 1), so each call moves closer to zero.

8. Print the hollow diamond for n equal to 5. A cell is a star when its row distance from the centre plus its column distance from the centre equals n // 2. The double slash is integer division, which drops the fraction, so 5 // 2 is 2. The centre is row 2 and column 2, counting from 0. Predict the output first.

Show the answer

The output is *, then * *, then * *, then * *, then *. Each row is shown here without its trailing spaces. The centre is row 2 and column 2, and n // 2 is 2. A cell is a star when its row distance plus its column distance is 2, which traces out the outline of a diamond. Count the stars: 1, 2, 2, 2 and 1 make 8. The program below prints this result.

9. Count the total stars in the diamond for n equal to 4, without printing it. Explain how the top and bottom halves contribute.

Show the answer

The total is 25. The top half has rows of 1, 3, 5 and 7 stars, which add to 16. The bottom half has rows of 5, 3 and 1 stars, which add to 9. The two halves sum to 25.

10. Explain why the recursive function below will never stop, then rewrite it so it stops when n reaches zero.

def spin(n):
    print(n)
    spin(n)

Show the answer

The call spin(n) passes the same value again, so n never changes and the base case is never tested. The program prints 4 many times, then fails with RecursionError: maximum recursion depth exceeded. The fix is a base case and a smaller input:

def spin(n):
    if n == 0:
        return
    print(n)
    spin(n - 1)

With n equal to 3 this prints 3, 2 and 1, one per line.

Summary

• A diamond is a pyramid followed by an upside-down pyramid. The bottom half counts down from n - 1, so the widest row prints only once.
• A butterfly is a triangle mirrored across a vertical gap. The gap is 2 * (n - i) spaces, which is zero in the widest row.
• A helper function builds or prints one row, so the main part of the program only chooses which rows to use and in what order.
• A recursive function calls itself. It needs a base case that stops the calls, and each call must move closer to that case.
• The position of the print relative to the recursive call decides the order of the rows. Before the call prints the largest first, and after the call prints the smallest first.
• A recursion with no base case stops with RecursionError, and the traceback shows the same line repeated.