Welcome to Lesson 7!
Learning ObjectivesBy 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
 Midterm one next week
 Quiz 2 after the break.
 Lab 4 posted  slightly easier as I expect you to be studying for the midterm
 Project Report 1 due next class
 Please see me at break if you did not get on a project team
 Please see me at break if you did not find a partner for Lab 3
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?
 How would you write insertIterator for a doubly linked list?
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.
Image Source.
The Most Interesting Man in the World's Secret Power: 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
Step 2 – Subdivide by three
Step 3 – Subdivide again by three
Step 4 and beyond – Keep subdividing by three
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.
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 subtasks, 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 nonnegative 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 subproblems 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 (n1); //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().
 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 nontrivial case. How could you break the problem down into smaller and smaller subproblems, where the subproblems are similar.
 e.g. n! = n * (n1)!, while (n1)! = (n1) * (n2)! etc.
 Call the function on this smaller subproblem and return the result.
 e.g. return n * factorial(n1);
 After you write your recursive function, it is important to confirm that the following three properties are satisfied:
 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.
 Each base case returns the correct value for that case.
 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 rewrite 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.
Upcoming Assignments  Lab 4 due one week from today
