Welcome to Lesson 6!


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 function 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.
  • What is binary search and how does its recursive implementation work?
  • How do you print a linked list in reverse?

Announcements
  • Women in Computer Science Club meeting on Wednesday from 12:30-1:30pm
    • We will attend a career panel in Conference Room B
    • Post meeting at 1:30pm if you are interested in taking a leadership role in the club
  • Project Report 1 due
  • Return Quiz 2
  • Next Quiz on Wednesday - 3 repeat questions from Quiz 2 + 3 new questions
    • For those who did well, how did you study? Any advice for your classmates?
  • Midterm 1 Review Guide now posted
    • 1st midterm one week from Wednesday

Review of Stacks vs Queues

With a partner, answer the following questions:
  • On a sheet of paper, draw a Queue and a Stack, including labeling its front and end or top (respectively)
    • Note: your drawing should reflect the specifications for the Queue and Stack that were set out during the last class
  • What images did we discuss in class to represent the Stack and Queue?
  • FIFO and LIFO. What do they stand for and which one is associated with a Queue?
  • How would you write the enqueue and push functions for a Queue and Stack?


Puzzle Question
This question comes from an Amazon interview. Find a partner and discuss the following:
  • How would you print a linked list in reverse?


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..."


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.


Introduction to Recursion

  • Any function that calls itself is considered recursive.
  • A recursive function solves a problem by calling a copy of itself to work on a smaller problem.
    • Remember: "Many hands make light work"
  • Each time, the function 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 function terminates. Therefore, you need to ensure that your function ends when it reaches the base case.


Why Recursion?

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

Group Activity: Let's Give Recursion a Try!
  • Let's suppose that we need to find 37! (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, 37! = 37 * 36 * 35 * 34 * .... * 1.
  • That would be the equivalent of doing 37 different multiplication operations.
  • If we need to solve this problem and don't have a calculator with a factorial button, then our fingers might get tired from pressing so many keys.
  • Let's use the power of recursion (and crowdsourcing) to help us solve this problem! 
  • Each person in the class is going to be tasked with multiplying just two numbers together. (We will pass around the calculator).
  • One person is going to be our base case.
  • The base case is the number at which our multiplication should stop. What number will that be?
  • To figure out your number, we will go around the room and break the problem down into ever smaller factorials.
  • Then, we will build the solution up by multiplying the numbers together.
  • The first person will begin by saying : "37 factorial  is 37 * 36 factorial"
  • When we reach our base case, we will start multiplying the smaller sub-problems together until we reach the solution.
  • At this stage, each person will multiply their number by the running total, announcing the result for their subproblem. For example: One person will say "5 * 24 = 120." She or he will then pass the calculator to the next person.
  • Questions? Let's begin!


Recursion Example: Factorial

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

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

...

cout << factorial(4); //prints 24

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


Recursion: Behind the Scenes in Memory
  • Each time a recursive call is made inside a function, a copy of the local variables and parameters for that function, as well as the return address, are pushed onto the stack memory.
  • Remember how a stack works?
  • This stack is called the function call stack.
  • The data pushed onto the stack is known as the stack frame.
  • When the function returns, the local variables, parameters and return addresses are popped from the stack frame.
  • If the recursive function 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 function call stack containing stack frames for two different functions, DrawLine() and DrawSquare().File:Call-stack-layout.svg
  • Below is an example of the function call stack for the recursive factorial function.
  • With the first call to factorial, the function 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.

Format of a Recursive Function

  • The general format of a recursive function looks like this:
returnType recursiveFunction(parameter)
{
    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 recursiveFunction(updated parameter)
}

How To Write a Recursive Function
  • 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 function on this smaller subproblem and return the result.
    • e.g. return n * factorial(n-1);
  • After you write your recursive function, 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 function is the correct value. This is the magic of recursion.

Group Activity: Recursion Practice
  • We are going to practice our recursion skills on the CodingBat website.
  • Although these exercises are in Java, the code that you will need to write is identical to C++, so just ignore the language.
  • As a minimum, write the following 5 functions:
    • fibonacci
    • bunnyEars
    • bunnyEars2
    • powerN
    • sumDigits


Tracing the Classic Recursive Fibonacci Function


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 our factorial function, using a loop:
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 expensive 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.


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

  • With your partner, answer the learning objective questions from the beginning of the lesson.