Welcome to Week 4  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 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.
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.
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 subtasks, 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 nonnegative 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 subproblems.
 Once, we knew the answer to one of the subproblems, we were able to work our way back up to solve each subproblem 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.
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().
 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 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 method on this smaller subproblem and return the result.
 e.g. return n * factorial(n1);
 After you write your recursive method, 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 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 rewrite 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
