Recursion in java for beginners part-1

What is recursion?

In simple words we can say that recursion is a method that calls itself.

Why recursion?

• It helps us solving bigger and complex problems in an easy way.
• Solving a problem directly with iterative approach(using loops) is difficult so we use recursion.

Okay so you have mentioned what is recursion and why is it important but tell me the main thing. How can I write a recursive method myself?

How to write a recursive method?

So, to write a recursive method you need to find three things.

1. Base condition
2. Body of the method
3. Return type

Ahh, what are these terms I'am not understanding anything. What is a base condition and this return type how to know where should I use them and what to do with it? So confusing please make it clear.

Wait a moment. Let me explain..

Base condition

So, the base condition is a specific case that can be solved without using the recursive calls. It is represented by the answers we already know. Simply it is a condition where the method will stop making new calls.

Ok OK I understood this. But I have one question in mind.

What if I don't use a base condition?Will it have any difference if I don't use a base condition?

The answer to your question is a big YES. If you don't use a base conditon, the method will keep calling itself again and again and the Stack will keep filling. Since we know that every call of a method takes some memory so the method will exceed the limit of the system's memory resulting in StackOverFlowError. Yes, the name of that famous website came from here only. And return type is simply the answer that we want from the method we are calling.

Let me explain base condition with some examples. It will be more clear to you.

If you want to calculate nth Fibonacci number the base condition in that case is F(0)=1 and F(1)=1.

In case of Factorial the base case is factorial(1) = 1.

See, in both of the above situation the base conditions are the cases that can be solved without using the recursive method.

You are confusing me everytime. Now what is this stack thing you have mentioned?

To understand stack you have to read my previous blog where I have briefly explained stack. And I will be writing a detailed blog on stack soon.

Recurrence relation

Recurrence relation or the body of the method is simply that formula that repeats itself everytime whenever the method calls itself.

Let me give you some examples

The recursive case for fibonacci numbers is: F(n) = F(n-1) + F(n-2).

The recursive case for factorial of a number is: factorial(n) = n × factorial(n – 1)

I finally understood what is recursion and how to write it.. ｡^‿^｡

But I still have one doubt how would I know if I can solve a particular problem with recursion or not?

How to find if a problem can be solved by recursion or not?

To know whether you can solve a problem by recursion or not first you need the understand the problem. You need to identify if you can break down the main problem into smaller problems and see if the smaller problem is the same as the original problem or not. For example if you want to find the sum of first 10 numbers does it helps to calculate a sum of first 9 numbers? This may be a guide to see if Recursion can be used or not.

Great, I got a problem I broke it into smaller parts now I know I can solve this problem by recursion. Still I have one small question. After understanding that a particular problem uses recursion. How can I approach the problem? What are the steps to solve the problem?

How to solve a recursion problem?

As I have mentioned above. Finding the base case for any recursive problem is the very first step towards writing a recursive method in Java or in any other programming language.

After that you need to find a way to call it's recurrence relation and where to use the result that is returned by the relation. Sometimes you may need to add, mutiply, divide or subtract depending upon the problem. This will be more clear after you practice some question.

This is the first part of this blog. In the next part I'll explain how to approach and solve questions with recursion. I'll be taking some questions and will solve all of them using the same approach to get you hands on in recursion.