U10 Recursion P1 Student

10.1 Recursion

A method calling itself to repeat a certain number of times.

Popcorn Hack: What is recursion?

When a function calls itself to solve a problem by breaking the problem down into smaller subsections.

Vocabulary

Base Case - this sets the termination condition for when the recursion will stop
Formal Parameters - arguments within the method (local variables)

Method Calling Itself

We will first be looking at how a method can call itself.

```java /* DO NOT RUN THIS if you do run this accidentally press ctrl + c twice */

public class Recursion1 { public static void recursionCount(int n) { // original method definition System.out.println(n); recursionCount(n - 1); // calling the method again }

public static void main(String[] args) { recursionCount(3); // original call of the method } }

Recursion1.main(null); In this example, you will receive an overflow error because the method is calling itself infinitely. To avoid this, you would create a __ __.

A base case usually uses an if-then statement to turn the loop off after a certain condition is met.

java Copy code public class Recursion2 { public static void recursionCount(int n) { if (n <= 0) { // added base case, telling the program to stop when n is less than or equal to 0 System.out.println(“done”); } else { System.println(n); recursionCount(n - 1); // method recursion } }

public static void main(String[] args) { recursionCount(3); // calling original function } }

Recursion2.main(null); Popcorn Hack: Create your own quick recursive program.

java Copy code // Add code here

public class RecursiveFactorial { public static void main(String[] args) { int n = 5; // Change this value to calculate the factorial of a different number long factorial = calculateFactorial(n); System.out.println(“Factorial of “ + n + “ is “ + factorial); }

public static long calculateFactorial(int n) {
    if (n == 0) {
        return 1; // Base case: 0! = 1
    } else {
        return n * calculateFactorial(n - 1); // Recursive case: n! = n * (n-1)!
    }
} } Calling With Different Parameters You can also call the method with multiple different arguments, also known as local variables.

In this example, we call an integer and string.

java Copy code public class Recursion3 { public static void recursionPrint(int n, String a) { // formal parameters are within this method if (n <= 0) { // base case System.out.println(“done”); return; }

System.out.println("n = " + n + " a = " + a); // printing each variable with each call of the method

String addChar = a + "!"; // mutating string with each recursion
int addN = n - 1; // mutating integer with each recursion

recursionPrint(addN, addChar); // recursive function   }

public static void main(String[] args) { recursionPrint(5, “test”); // initial call } }

Recursion3.main(null); Here we just __ each string and subtract one from every previous number.

Capturing Progression Through Recursion You can also capture the progression through recursion. This is useful for doing specific tasks in specific steps through recursion.

java Copy code public class Recursion4 { public static void recursionCount(int n, int progress) { if (n <= 0) { System.out.println(“done”); } else { if (n == progress) { System.out.println(“Reached halfway through the array.”); // special action done only when the program has reached a certain point } System.out.println(n); recursionCount(n - 1, progress); // recursive call } }

public static void main(String[] args) { int n = 6; int progress = n / 2; // progress is set to half of the array length recursionCount(n, progress); // initial call } }

Recursion4.main(null); Popcorn Hack: What other situations could we use capturing progression for?

Capturing progression is good for monitoring algorithm efficiency, measuring code optimization, and evaluating software development.

Converting Recursion to Iteration Any recursive process can be made iterative, however this is not needed for the AP test. It is, however, still useful.

Recursive Version java Copy code public class Recursion5 { public static void recursionCount(int n) { if (n <= 0){ System.out.println(“done”); } else { System.out.println(n); recursionCount(n - 1); // recursive function } }

public static void main(String[] args) { recursionCount(3); // initial call } }

Recursion5.main(null); Iterative Version java Copy code public class Iteration { public static void iterationCount(int n) { for (int i = n; i >= 1; i–) { // using a for loop to iterate, notice we go only so i is greater than 1 and not 0 System.out.println(i); } System.out.println(“done”); }

public static void main(String[] args) { iterationCount(3); // same initial call } }

Iteration.main(null); Popcorn Hacks: Why do we go only so i is greater than or equal to 1 and not 0?

It is due to the i >= 1 condition which causes it to start at 1.

Traversing With Recursion You can traverse many things with recursion. Here I will show traversal through a string, array, and an ArrayList object.

String Traversal You can traverse through a string, finding a specific character in the string.

java Copy code public class FindChar { public static boolean findChar(String s, char target, int index) { if (index >= s.length()) { // checks for if the index we are looking for is greater than the word length return false; }

    if (s.charAt(index) == target) { // checks for if there is a character at the index we are searching
        return true;
    }

    return findChar(s, target, index + 1); // recalls the method, recursion
}

public static void main(String[] args) {
    String sampleString = "words"; // example string
    char targetChar = 's'; // character we are looking for

    System.out.println("Sample String: " + sampleString);

U10 Recursion P1 Student • 15 min read

Description

10.1 Recursion

Vocabulary

Method Calling Itself