Recursion (P3) - Part 1

Recursion

10.1) Recursion

Skill 5.A (10.1.1)

What is recursion?

Recursion is when a function calls itself directly or indirectly over and over again in order to solve a problem. It is very much like a loop, with few differences.

Void Recursive Method

Demonstration in code

public static void simpleRecur(int n) {
    System.out.println(n);
    
    if (n > 2) {
        simpleRecur (n-1);
    }
}
simpleRecur(5);

A void recursive method simply means that the recursion will not return any values.

You can see here that simpleRecur calls itself, and will continue to call itself until n is less than or equal to 2, this condition is called the base case.

The College Board will require you to be able to trace out the steps that are taken in a recursive program, so let’s trace out what the program does in a table.

Demonstration

Before looking at the table, let’s do a small demonstration with 4 volunteers:

• Person 1: Take in the number and give to the next person
• Person 2: Write the number given to them on the whiteboard
• Person 3: Check whether the number is greater than 2
• Person 4: Subtract one from the number to give to person one

Call Stack	Variable trace for call
simpleRecur(4)	n = 4 The function will first print out 4, because of the print statement. Since 4>2, the function will call itself again with the parameter n-1 (which is 3)
simpleRecur(3)	n = 3 The function will first print out 3, because of the print statement. Since 3>2, the function will call itself again with the parameter n-1 (which is 2)
simpleRecur(2)	n = 2 The function will first print out 2, because of the print statement. Since 2=2, the function will NOT call itself again and stop here.

Infinite Recursion

Infinite recursions are exactly what they sound like, recursions but they go on infinitely.

public static void infRecur(int n)
{
    System.out.println(n);
    
    if (n>2) {
        simpleRecur2 (n+1); 
    }
}

Call Stack	Variable trace for call
infRecur(3)	n = 3 The function will print out 3 first Since 3>2, the function will be called again with the parameter n+1 (4).
infRecur(4)	n = 4 The function will print out 4 first Since 3>2, the function will be called again with the parameter n+1 (5).
infRecur(5)	n = 5 The function will first print out 5, because of the print statement. <br>You can see the pattern, this recursion will continue forever.

Non Void Methods

Non Void Recursive Methods are recursions, but a value is returned.

public static int simpleRecur3 (int n)
{
    if (n==0) {
        return 0;
    }
    
    return n + simpleRecur3 (n/2);
}

Call Stack	Variable trace for call
simpleRecur3(4)	n = 4 n is not zero, therefore it moves onto the next line. the function will return 4 + (the next steps).
simpleRecur3(2)	n = 2 n is not zero, therefore it moves onto the next line. the function will return 2 + (the next steps).
simpleRecur3(1)	n = 2 n is not zero, therefore it moves onto the next line. the function will return 2 + (the next steps).
simpleRecur3(0)	(note the numbers are int, java treats ½ as zero) n = 0 n is zero, therefore the function will not be called again and return zero.
Summing together:	4 + simpleRecur3(2) + simpleRecur3(1) + simpleRecur3(0) 4 + 2 + 1 + 0 = 7

Knowing how to trace a recursion and its inner workings is one of the skills required for AP exams.

Popcorn Hack 1 - Factorial

Introduction

Factorials are a common technique which may be easy to implement using recursion. This is due to their repetitive nature in terms of multiplication. Please complete the factorial method below. The comments in the code may help you out a bit.

// 5! = 5 * 4! = 5 * (5 – 1)!
// 4! = 4 * 3! = 4 * (4 – 1)!
// ...
// 1! = 1

public static int factorial(int target) {
	if (target <= 1) {
		return 1;
	}
	return target * factorial(target - 1);
}
factorial(5);

Skill 5.A (10.1.2)

Review from 10.1.1

• A recursive method is a method which calls itself

Anatomy of a Recursive Method (CON-2.0.2)

• A recursive method must have at least one base case and at least one recursive call
  • What is a base case? A base case is a condition which breaks the recursive function
  • It is ABSOLUTELY important to have a base case or else this happens
  • Recursion Moment
  • 
  • Having two calls is also acceptable

Method Refresher (CON-2.0.3)

• Like every other method, recursive methods have their local variables and parameters. Local variables can be helpful when constructing a base method to exit out of the recursive method. Formal parameters are also needed.
• A local variable is only accessible to the inside of a function
• 

Parameters Capture the Progress of the Recursive Function (CON-2.0.4)

• Every parameter in a recursive system is sort of like a capture. It gives us the information we need to determine the next element in a sort of series of captures.
• This stems from the definition of a method or function with its inputs and outputs.
• Example: I want to make a program to reverse a string in Java. I can write down each call and slowly once the calls reach an end, I can start tracking the print statements BACKWARDS

Recursion and Iteration (CON-2.0.5)

• Every iterative approach has a recursive solution
• Recursion is just another way of looping. In assembly, loops work through instructions such as jmp which in easy terms, jump to another line of code. This is how loops work. Just constant jumping.
• There is another instruction called ret and another called ret which basically also jumps to other parts of the program. Because they are so similar tojmp, they can be used to solve the same problems.

Popcorn Hack 2 - Recurse Through an Arrays

Introduction

Using your knowledge of local and global variables, create a recursive method which recurses through an array instead of iterating through it

// Pro tip: Think of why the index is stored as a parameter
// What are parameters usually used as?

public static int sumArray(int[] arr, int index) { 
    if (index == arr.length) {
        return 0;
    }
    return arr[index] + sumArray(arr, index + 1);
}

sumArray(new int[] {1, 2, 3, 4, 5}, 0);