Welcome to Week 4 - Lesson 7!


Learning Objectives
By the end of this class, you should know...
  • How to define Recursion:
    • Recursion
      • Recursion
        • Recursion
          • Recursion
            • Recursion
              • Recursion
                • Base case: Okay you get the point
              • Return
            • Return
          • Return
        • Return
      • Return
    • Return
  • What is the difference between Iteration and Recursion?
  • What is the method call stack and what is a stack frame?
  • How does recursion make use of the stack memory?
  • What is a stack overflow error?
  • How to solve some fundamental recursive problems.
  • How do you print a linked list in reverse?


1. Reflection
This question comes from an Amazon interview. Discuss the following:
  • How would you print a linked list in reverse?


2. Recursion

Simple Definition

  • From Miriam Webster's Dictionary: "a computer programming technique involving the use of a procedure, subroutine, function, or algorithm that calls itself one or more times until a specified condition is met..."
  • In other words, a recursive method is one that calls itself until a condition is met.


2.1. Fun With Recursion

"To understand recursion, you must first understand recursion." ~unknown


Try Typing the Word "recursion" into Google and See What Happens.


Find out what recursion is with this Google Easter Egg

Image Source.


The Most Interesting Man in the World's Secret Power: Recursion

The most interesting man in the world: "I don't often repeat myself, but when I do I use recursion"
image source


Fractals (A fractal is a mathematical set that exhibits a repeating pattern displayed at every scale) can be generated using recursion, as in the examples below.

Here is an example of how to create a fractal, known as the Sierpinski triangle. Content from a blog post on fractals.

Step 1 – Take Triangle

Triangle - step 1

Step 2 – Subdivide by three

Triangle - step 2

Step 3 – Subdivide again by three

Triangle - step 3

Step 4 and beyond  – Keep subdividing by three

Triangle - step 4  Triangle - step 5  Triangle - step 6


Computer generated fractals can be very complex, such as the one seen here.


video


Fractals are common in nature

Snowflakes are fractals. Image source.

Romanesco broccoli (a variant of cauliflower) is a fractal - golden spiral. Image source.

Maz Kanata’s Romanesco Apple Bacon Quiche / Check out our blog for lots of Star Wars Party food recipes and downloadable labels! Great for a Birthday Party or a May the Fourth be with you Party. / #starwars #starwarsparty #theforceawakens #maythefourthbewithyou #starwarsbirthday #starwarsfood #quiche #romanesco #mazkanata #maz #rey #takodana #apple #bacon #recipe / maythefourthbewithyoupartyblog.com

image source and recipe!

Recursion humor

Recursive Russian nesting dolls. Image Source.

Recursive Hulk Hogan.Image Source.


3. Introduction to Recursion

  • Any method that calls itself is considered recursive.
  • A recursive method solves a problem by calling a copy of itself to work on a smaller problem.
    • Remember: "Many hands make light work"
  • Each time, the method calls itself on a slightly simpler version of the original problem. This is called the recursive step.
  • It is important to make sure that the method terminates. Therefore, you need to ensure that your method ends when it reaches the base case.


3.1. Why Recursion?

  • Recursion is a useful alternative to loops in iterative code.
  • A recursive method can be shorter and easier to write than the iterative version of the same method.
  • Recursion is especially useful when dealing with tasks that can be broken down into similar sub-tasks, such as the factorial example below.

3.2. Group Activity: Let's Give Recursion a Try!
  • Let's suppose that we need to find 5! (37 factorial)
  • Recall that, in mathematics, the factorial of a non-negative integer n, denoted by n!, is the product of all positive integers less than or equal to n.
  • Therefore, 5! = 5 * 4 * 3 * 2 * 1.
  • However, we can consider 5! to be 5 * 4!
  • If we know 4! then it is an easy multiplication problem
  • If not, we could break 4! down to 4 * 3!
  • And, 3! is 3 * 2!
  • Finally, 2! is 2 * 1!
  • Now, 1! is 1. We have finally reached a factorial problem that we know the solution to.
  • We can thus work our way back up
  • 2! = 2 * 1 = 2
  • Therefore, 3! = 3 * 2 = 6
  • Now, 4! = 4 * 6 = 24
  • Finally, 5! = 5 * 24 = 120
  • The above is a recursive approach to this problem, wherein we broke the original problem into ever smaller sub-problems.
  • Once, we knew the answer to one of the sub-problems, we were able to work our way back up to solve each sub-problem until we reached the final solution to our original problem.
  • Note we could have stopped at 0! = 1 or 2! = 2.
  • Our choice of base case (0, 1, or 2) has little impact on the overall efficiency of our solution when dealing with large factorial problems.
  • We will trace this example on the board.
Solutions to factorial problems from 0! to 20!
image source


3.3. Recursion Example: Factorial

  • Let's take the last exercise and turn it into a recursive method.
  • Below is an example of a recursive factorial method.

public static int factorial(int n) {
    if (n == 1) //our base case
        return 1;
    else
        return n * factorial (n - 1); //method calling itself on an ever easier problem.
}

...

public static void main(String[] args) { //calling method

    System.out.println(factorial(4)); //prints 24

}

  • The diagram below will help us to visualize what happens when we call the factorial method with 4 as the parameter.


3.4. Recursion: Behind the Scenes in Memory
  • Each time a recursive call is made inside a method, a copy of the local variables and parameters for that method, as well as the return address, are pushed onto the stack memory.
  • Remember how a stack works?
  • This stack is called the method call stack.
  • The data pushed onto the stack for each method call is known as a stack frame.
  • When the method returns, the local variables, parameters and return addresses are popped from the stack frame.
  • If the recursive method fails to find a base case (infinite recursion), a new stack frame will be pushed onto the stack until the dreaded stack overflow occurs (i.e. the stack memory runs out of space).
  • Because space is taken up on the stack for each recursive call, recursion is generally considered an "expensive" solution, as it can require a lot of memory.
  • Below is a general example of a method call stack containing stack frames for two different methods, DrawLine() and DrawSquare().File:Call-stack-layout.svg
  • Below is an example of the method call stack for the recursive factorial method.
  • With the first call to factorial, the method call is pushed onto the stack frame, along with its local variables and the location to which it should return (a stack frame).



  • Then, with each successive recursive call, a new stack frame is pushed onto the stack, and the stack pointer gets moved down:
  • Now, we have reached the base case so we return and pop the top stack frame.
  • This process repeats until the last call to factorial returns to main.

3.5. Format of a Recursive Method

  • The general format of a recursive method looks like this:
public returnType recursiveMethod(parameter list)
{
    if (test for base case)
        return base case value
    else (test for another base case if needed)
        return other base case value
    else
        return some work and a recursive call to recursiveMethod(updated argument)
}

3.6. How To Write a Recursive Method
  • Think of how to solve the problem for small or trivial cases. Make this case your base case.
    • e.g. You know that 1! is 1.
    • Place this base case inside of the test condition of an if statement and return the trivial result.
  • Then consider a non-trivial case. How could you break the problem down into smaller and smaller subproblems, where the subproblems are similar.
    • e.g. n! = n * (n-1)!, while (n-1)! = (n-1) * (n-2)! etc.
  • Call the method on this smaller subproblem and return the result.
    • e.g. return n * factorial(n-1);
  • After you write your recursive method, it is important to confirm that the following three properties are satisfied:
  1. There is no infinite recursion. A recursive call may lead to another recursive call and that may lead to another and so forth, but every such chain of recursive calls eventually reaches a stopping case.
  2. Each base case returns the correct value for that case.
  3. For the cases that involve recursion: If all recursive calls return the correct value, then the final value returned by the method is the correct value. This is the magic of recursion.

3.7. Group Activity: Recursion Practice
  • We are going to practice our recursion skills on the CodingBat website.
  • As a minimum, write the following 5 methods:
    • fibonacci
    • bunnyEars
    • bunnyEars2
    • powerN
    • sumDigits


3.8. Tracing the Classic Recursive Fibonacci Method


3.9. Recursion vs Iteration

  • In many cases, either recursion or iteration (using loops) can be used to solve a problem.
  • In general, both approaches are used to solve tasks by breaking them into pieces, and then combining these pieces to produce the result.
  • For example, we could re-write the factorial method from above, using a loop:
public static int factorial(int n)
{
    int product = 1;
    while (n > 1)
    {
        product = product * n;
        n--;
    }
    return product;
}
  • Recursion is often the most intuitive and elegant solution.
  • It is also easy to prove a correct recursive solution using a technique called proof by induction.
  • However, it can be more memory intensive than the iterative solution because of the large amount of memory required.
  • Tail recursion, which you will learn about in a future class, reduces the amount of memory used, thereby rendering the recursive solution competitive with the iterative solution in terms of memory used.


3.10. Some Important Algorithms That Use Recursive Solutions

  • Sorting Algorithms: Merge Sort, Quick Sort
  • Searching Algorithms: Binary Search
  • Tree Traversals: InOrder, PreOrder, PostOrder
  • Graph Traversals: Depth First Search
  • Divide and Conquer Algorithms
  • Don't worry if you don't know what these are! By the time this class is finished, you will understand all of them, and will also feel much more confidant doing recursion.

Wrap Up
  • Answer the review questions on Canvas for today's lesson

Upcoming Assignments

  • Lab due Monday
  • Study for your Midterm