Last edited 12/12/12 by wdsouza2@illinois.edu

A Lesson on Recursion with a Modified Menger Sponge




Welcome! Here's an Overview

The purpose of this project is to provide a visual demonstration of recursion using the Menger Sponge with a special modification. After spending several weeks developing the functions that would create a Menger Sponge of n iterations (and making it functional in the CUBE), the next step was to play with recursion so that it could be selectively suppressed. This means that the user would be able to specify the likelihood of recursing (due to my own programming limitations, this number was limited to <5%. More on this later) and then the Menger Sponge would be generated. If any of the 20 cubes in the first iteration of the Menger Sponge were to be in the lucky <5%, the cube would split itself into another Menger Sponge and the process would repeat.
Perhaps a future upgrade to this project would be to allow the recursion to stop at a certain point without destroying the cube. The issue I ran into while programming this project was that if I entered a probability of recursing that was too likely (which I found to be around 7% or higher), the cube would have a significant chance of recursing too many times and crashing the program. What should be happening is to allow the recursion to stop at around 4-5 iterations so that the cubes don't become to small and the recursion doesn't continue ad infinitum.

A link to the initial project proposal is at the bottom of this web page, along with other useful links.

A brief review upon seeing my final project run: If I had more time I would like to experiment with the randomness and create limits so that I can increase the chances of recursing without causing an overflow of recursion. Right now I have to run my program anywhere from 1-5 times before seeing a good depiction of the selective suppression and showing recursion in multiple stages (pictures below).

Guide to the Files in my CubeReady Folder

  • cube.py : The parent file for most of the methods used in szgcube. When run on a computer, creates a Menger Sponge of 3 iterations in Torus-style navigation scrolling, which makes it difficult to see the whole cube. This is okay because cube.py is not my final project but only contains useful functions.
  • szgcube.py : THE FINAL PROJECT FILE. This project uses a specified probability (4% in my case) that determines if each cube in the Menger Sponge (which begins at 1 iteration) will recurse. If the probability is met (the basic operation is that a successful case would generate a list of 20 sublists for each smaller cube) then the cube recurses and a new Sponge is generated in the dimensions of the old cube. If the condition is not met, the cube is assigned an empty list and recursion ends. This process repeats for every cube in the Menger Sponge, for every iterative level, until all cubes are assigned an empty list. Usually this process doesn't go further than 3 iterations just due to probability, but there are rare cases with 5 or higher iterations.
  • meng.py : This is a slightly modified and renamed version of cube.py, which mainly exists as the companion to szgmeng.py just to keep the two projects separate. Nothing interesting to see here.
  • szgmeng.py : This is a program I created mainly for demonstration purposes. It does not use the selective recursion. The purpose of this program is simply to generate 4 levels of the Menger sponge (0,1,2,3 iterations, where 0 is a normal cube). When the program runs, you begin inside a rainbow-colored cube. You may move forward with the mouse keys to advance toward the Menger Sponge of 1 iteration, and then keep going toward the mighty 2- and 3-iteration Sponges!
  • szgfirstcube.py : This program creates a simple Menger Sponge of 3 iterations, no special add-ons or tricks. This was the "beta" version of the project, and has run successfully and efficiently in the CUBE after being worked on by Dylan and Zach to implement Display Lists. This program was demonstrated to CHP students in the Fall 2012 Student Adventure Series at the ISL.

    • Progress Report

    The Moment You've Been Waiting for...Cool Picture Thingies!


    Below are three representations of the Menger Sponge in 3D in my beta version of szgcube.py. You may view them all together in szgmeng.py!




    Below is an image from my final program szgcube.py demonstrating recursion on one of its large cubes. As you can see, despite a probability of 4% in favor of recursion success, the cube managed to recurse twice more on two smaller cubes each, reaching the 4th iteration (the tiniest Menger Sponge).


    Below is another image from szgcubempy, demonstrating the furthest level of recursion I managed to observe in my multiple runs of the program:
    A single cube reaching the 5th iteration (may be difficult to see the smallest one, but try counting the iterations yourself. Remember that the biggest cube is already 1 iteration). Notice that another cube adjacent to it also managed to hit the 4th iteration.



    Relevant Links and Credits