Lesson 1

Recursion Refreshment in Java


Hello, fellow explorer! Today, we will unravel the mystery of "Recursion" — a concept as enthralling as the patterns formed by two mirrors facing each other. We aim to decipher recursion, understand its inner workings, and master its application in Java.

Understanding Recursion

Consider a stack of books. Want the bottom one? You'll need to remove each book above it, one by one. It's a recurring action — an example of recursion. In programming, recursion encompasses a function calling itself repeatedly until a specific condition is met, similar to descending stairs one step at a time until you reach the ground.

Here's a simple Java function illustrating recursion:

1public class Main { 2 public static void recursiveFunction(int x) { 3 if(x <= 0){ // Termination condition --> base case 4 System.out.println("Base case reached"); 5 } else { 6 System.out.print(x); 7 recursiveFunction(x - 1); // Recursive function call --> recursive case 8 } 9 } 10 public static void main(String[] args) { 11 recursiveFunction(5); 12 } 13} 14/*Output: 155 164 173 182 191 20Base case reached 21*/

This function keeps calling itself with x getting lower by one until x <= 0, which is our base case. At this point, it stops the recursion.

Defining the Base Case

The base case acts like a friendly signpost, telling the recursion when to stop. In our book stack example, reaching a point where no more books are left to remove serves as the signal. Similarly, x <= 0 is our base case in our function. The base case is crucial as it prevents infinite recursion and related errors.

Defining the Recursive Case

The recursive case is an essential aspect of recursion — the rule responsible for creating smaller versions of the original problem. Each call brings us a step closer to the base case. Let's use the process of calculating a factorial as an illustrative example.

To find a factorial, we multiply a number by the factorial of the number minus one, and repeat this process until we get to one (our base case):

1public class Main { 2 static int factorial(int n){ 3 if(n == 1){ // base case 4 return 1; 5 } else { 6 return n*factorial(n-1); // recursive case 7 } 8 } 9 public static void main(String[] args) { 10 System.out.println(factorial(3)); // we expect 6 (3 * 2 * 1) 11 } 12}

In this case, we call factorial(3), it returns 3 * factorial(2), where factorial(2) returns 2 * factorial(1). As factorial(1) is a base case, it returns 1. As a result, the whole recursion chain returns 3 * 2 * 1.

Tips for Thinking Recursively

To think recursively, visualize the problem like an onion. Peeling each layer brings you closer to the center. The center of the onion represents the base case, and the peeling process denotes the recursive case.

Remember that a complex problem often contains smaller, simpler sub-problems. You can trust these sub-problems to be solved correctly, culminating in an elegant solution.

Another Example of Recursive Function

Let's develop a function that calculates the sum of an integer's digits. Normally, it would involve using a while loop, but with recursion, it is done much more easily:

1class Main { 2 static int sumOfDigits(int num) { 3 // Base case: if num is less than 10, return num itself 4 if(num < 10) { 5 return num; 6 } 7 else { 8 return num % 10 + sumOfDigits(num / 10); // Recursive case 9 } 10 } 11 12 public static void main(String args[]) { 13 System.out.println(sumOfDigits(12345)); // Will print out 15 (1+2+3+4+5) 14 } 15}

In this example, we use the same principle as with factorial calculation, but we pass num / 10 to the next recursion call, chopping off the last digit every time.

Conclusion and Lesson Summary

Let's pause here. We've unveiled the concept of recursion, determined the roles of base and recursive cases, and written a simple recursive function in Java. It's time to unlock its full potential through continuous practice, building a solid foundation for the upcoming sorting and searching algorithms lessons. Remember — practice illuminates knowledge. Happy experimenting!

Enjoy this lesson? Now it's time to practice with Cosmo!

Practice is how you turn knowledge into actual skills.