Deborah R. Fowler
Recursion in Python
Posted on Oct 13 2019Updated on Oct 13 2019
Recursion is defined as a function that calls itself. "To understand recursion, you must first understand recursion" Humor.
Seriously though, there are times to use recursion and many times not to. It is one way to solve a problem.
In order for this to work there must be some way of ending the recursion (just as a while loop needs a condition to end and if you forget you end up with an infinite loop, you want your recursive function to know when to quit). The structure of a recursive function involves a base case where the recursive call returns to where it was called. The computer "remembers" every previous state and returns, like every good function, to where it was called.
Advantages and disadvantages listed https://www.programiz.com/python-programming/recursion#what
If you scroll to the bottom of the page on the above article you will see a list of advantage and disadvantages.
Bottom line:
- PROS: provides and elegant and clean solution for a complex task that can be broken down into subtasks that involve recursion
- CONS: calls can be expensive and harder to debug
In Summary:
- Recursion is one way to solve a problem
- Recursion is when a function calls itself. It will need some end condition
- Structure: a base case, work toward a base case, recursive call (call itself)
- The computer "remembers" every previous state
- On the previous page is an example using sums. You will find in most textbooks/sites factorial, sum, fibonnaci. I wanted to create a few other python examples. You will also find Sierpinski's triangle (and I have used this as an example in numerous places on my site as well, both recursive (nice elegant solution) and iteratively.
- Sierpinski from the recommend online text (read this section on recursion - it is excellent!)
- My recursive version using Houdini and Python
- My iterative version using Houdini and Vex (vex does not support recursion so has to be created iteratively)
- Also included is my version using Houdini and L-systems
toward the bottom of the page
- In addition there is another classic example, the Koch snowflake (python versions bottom of this page)
- My version of Mandelbrot
in Houdini and Python
Here are some more basic visual examples to explain recursion:
Adding Random colors to the above code:
Have fun! Recursion is useful, but remember, it is meant for complex problems. You could make a square draw recursively but it is not recommended. That would not be a good use of recursion. Try some of your own, combine it with loops, explore! For example, how would you create these?