Recursion in Java

Hello students, welcome to Kwickprep. Can a method call itself, again and again, and still stop at the right time? Yes, and this idea is called recursion. Today we watch the call stack grow and shrink, learn the base case, and write factorial, Fibonacci, GCD and power. Then we use recursion on strings and arrays.

Let us define the term. A method that calls itself is called a recursive method, and the process is recursion. Each call works on a smaller version of the same problem. Think of nesting dolls, where every doll you open has a smaller doll inside. The smallest doll does not open, so the process stops there.

Here is our first recursive method, like a rocket launch countdown. Main calls count of three. It prints three, then calls count of two. That prints two and calls count of one, which prints one. Count of one then calls count of zero. Now the if condition is true, so it returns without calling again.

How does Java remember all these calls? It uses the call stack, a pile of boxes, one box per call. Each box is called a stack frame, and it holds that call's own copy of n. A new call is pushed on top of the pile. Only the top call runs, and every call below it waits. When a call finishes, its box is popped off, and the call below continues.

Now watch the stack for factorial of four, which is four into three into two into one. Step one, fact of four is pushed, and it waits for four into fact of three. Step two, fact of three is pushed on top, and it waits for fact of two. Step three, fact of two is pushed, and it waits for fact of one. Step four, fact of one does not call again, and it simply returns one.

Now the stack shrinks, and the answers travel back up. Step five, fact of one is popped and gives one. Step six, fact of two finishes two into one, which is two. Step seven, fact of three finishes three into two, which is six. Step eight, fact of four finishes four into six, and returns twenty four to main.

Every recursive method has two parts. The base case is the smallest problem, answered directly without calling again. The recursive case calls the method again, with a smaller input. Each call must move closer to the base case, like n minus one moving towards one. If there is no base case, the calls never stop, the stack fills up, and Java throws a StackOverflowError.

Here is factorial in code, with f short for fact. The base case says, if n is less than or equal to one, return one. The recursive case returns n into f of n minus one. So f of five is five into four into three into two into one. The program prints one hundred twenty.

In the Fibonacci series, each term is the sum of the two terms before it. The base case says, if n is zero or one, return n itself. The recursive case adds fib of n minus one and fib of n minus two. This method calls itself twice, so it is slow for large n. The loop in main prints the first seven terms, zero, one, one, two, three, five, eight.

The GCD, or greatest common divisor, is the biggest number that divides both numbers exactly. Euclid's rule says, gcd of a and b equals gcd of b and a modulus b. Modulus, the percent sign, gives the remainder. The base case says, when b becomes zero, the answer is a. Forty eight and eighteen become eighteen and twelve, then twelve and six, then six and zero. So it prints six.

Power means multiplying the base by itself, exponent times. Here b is the base and e is the exponent. The base case says, any number to the power zero is one. The recursive case says, b to the power e is b into b to the power e minus one. Two to the power five is two into two into two into two into two, which prints thirty two.

Pause the video and predict the output. This looks like our countdown, but the print comes after the call. So f of three waits for f of two, which waits for f of one. Nothing prints while the stack grows. The prints happen while the stack shrinks, so the output is one, two, three.

Recursion also works on strings. To reverse a word, reverse the rest of the word, then add the first letter at the end. The base case is an empty string, which is its own reverse. Substring of one gives the word without its first letter, and char At of zero gives the first letter. So reversing the word Java prints AVAJ.

For arrays, we pass an index that moves forward in each call. Here the array m holds marks of seventy, eighty five and ninety. The base case says, when i reaches the length, there are no marks left, so return zero. Otherwise, add m of i to the sum of the rest. The total marks printed are two hundred forty five.

Exams often ask you to compare recursion with a loop, which is called iteration. Recursion stops at the base case, while a loop stops when its condition becomes false. Recursion uses a stack frame for every call, so it needs more memory. But recursive code is often shorter and clearer, for problems like trees. A missing base case gives StackOverflowError, while a wrong loop condition runs forever.

Let us revise. Recursion means a method calling itself. The call stack pushes a frame on every call and pops it on return. The base case stops the calls, and the recursive case makes the input smaller. Factorial, Fibonacci, GCD and power are classic exam programs. For strings and arrays, solve the rest, then combine it with one element. Practise by tracing the stack on paper.