LSP- Recursion and Fractals Lesson

Recursion and Fractals

Recursion happens when we have a method that calls itself. It is another way to create iteration.  

One example of recursion is "The Song That Never Ends," an infinitely iterative children's song. The song appears in the album Lamb Chop's Sing-Along, Play-Along by the famous female puppeteer Shari Lewis. It is a single verse long song, written in an infinite-loop that keeps recalling itself.    

Another example of recursion is placing two mirrors in front of each other. This will result in nested images that are a form of infinite recursion.  

Unlike "The Song That Never Ends;" however, the recursion needs to end. A recursive method has two parts: the base case and the recursive call.    

There are two parts to a recursive method:

1. The base case in a recursive method is what will make the recursion stop. It relies on a boolean condition that will end the recursion when the condition is false. Once the base case is reached, the condition becomes false and the recursive method will stop calling itself.        
2. The Recursive call parameter information changes directions towards the base case. If the parameter data does not move toward the base case, the result will be an infinite recursion like "The Song That Never Ends."

Common Recursive Problem:  Calculate the Factorial

The factorial of any number n, usually written as n!, is defined as:  

n! = n * n-1

We could write a for loop in Processing to calculate the factorial.

The loop will iterate 4 times. The variable f is an accumulator variable that will be increased each time through the loop f=f*(i+1).  The variable f is returned at the end of the iteration.

Here is the same problem as a recursive call

To find fact(4), where the number 4 is passed through the parameter, we simply write out each step in the recursive computation:

1.   Identify the base case:   if n == 0   This will stop the recursion and return 1.  
2.   The recursive call has a parameter that will be directed toward the base case. In this example, the parameter argument is (4). Each time through the method it is reduced by one: n * fact(n-1).  
3. Write down the recursive call at each step.

Fractal

A fractal  is a geometric shape that is split into parts and produces repeated patterns that display at every scale. All fractals have a recursive definition. To learn more about fractals visit the Open Processing Links to an external site. website and the Processing Links to an external site. website located in the sidebar. You may not understand all the code at this time but they are fun to explore.

 

[CC BY 4.0] UNLESS OTHERWISE NOTED | IMAGES: LICENSED AND USED ACCORDING TO TERMS OF SUBSCRIPTION