What is Recursion? Java + DSA course || Blog 12

In Simple words, Recursion is a function calling itself again and again. Recursion is used to solve big and complex problems. It is used to solve problems which can be broke down into smaller pieces. Here, the space complexity is not constant because functions keeps calling itself. We can always convert recursive solutions to iterative solutions.

Lets learn recursion from basics.

For a quick overview, we will be learning:

• Basics of Recursion
• What happens in stack?
• Actual Recursion
• How to know if problem can be solved through Recursion?
  

 

• 

Basics of Recursion

Lets forget we are learning recursion. We just have to print numbers from 1 to 4. 

 

We use loops for iterating questions like printing numbers from 1 to 4 or run the loop until the condition becomes false, but what if we need to make a function for it. Why a function? -Functions allow you to break a program into more manageable pieces.

 

public class Printfourtoone{

public static void main(String[] args){

print1();

}

public static void print1(){

System.out.println(1);

print2();

}

public static void print2(){

System.out.println(2);

print3();

}

public static void print3(){

System.out.println(3);

print4();

}

public static void print4(){

System.out.println(4);

}

}

 

 

Here, we called function1(which prints 1) from the main function.

So main will call function1 AKA print1() . function 1 contains only 2 lines which is to print 1 and call 2nd function AKA print2().

Now, print2() will be called. It will print 2 and call print3().

print3() will print 3 and call print4(), It will just print 4 and stop.

So everything is printed.

When 4 will be printed, work of print4() function is done. It will come out of the loop and go to from where it was called i.e the 2nd line of print3(). 

 

Here, again there is nothing after "print4()" line. So it will come out of the function and go to where is was called from i.e 2nd line of print2().

 

Now, similarly it will come out from print2() and go to 2nd line of print1() function.

 

So, now it will come in main() function print1() and the program will end since there is nothing written after that in the main function.

This is the flow after the printing 1 2 3 4:

What happens in Stack?

We have learnt stack in detail the previous Blogs. Its just a place where data is stored. Imagine it as the collection of Books kept vertically. If you want a book you need to remove other books from the top to get that certain book.

Whenever a function has finished its work, it is removed from stack and points to where the function was called,

So, the flow was, main(),print1(), print2(), print3(), print4()..done.

 

After completion it is removed, so print4() removed, pointing towards print3(),completed so removes it, pointing towards print2(), completed so removes it, pointing towards print1(), completed so removes it, pointing to main(), completed so removes it.

 

So the stack is again empty.

Actual Recursion

If you check the above code, every function had two similar lines with increasing number.

What if we take 1 as argument and keep incrementing it until 4 is printed,  when it becomes five , we will break it like print5() function as it wasn't calling anyone. So now, the stack will start deleting it until all is deleted.

Lets try it.

 

Here, n is 1.if condition is false, it will print n.

 

Call itself with n+1 (1+1=2). Now, n=2.

Again it will print 2 and call itself with n+1(2+1=2). 

print 3 and call n+1(3+1=4). print 4 and call n+1(4+1=5).

Now, it satisfies the if condition, it will return from there.

So it will return to where it was called from, which is print1to4(4).

It will delete this stack.

Then print1to4(3)...  print1to4(2)... print1to4(1)... main()

The stack formation is same as in the video.

Here, the if condition is called the base case.it is very important in recursion. if we didn't used base case, the stack will keep on building causing the StackOverflowError.

How to know if problem can be solved through Recursion?

1. Check whether the problem can be broke into smaller problems
2. Form a recurrence relation..(we will see it in next Blog)
3. Try to draw the flow of program 
4. draw recursive tree..()in next blog
5. Use debugger it understand

In Next blog, we will solve various Recursion questions like binary search, fibonacci numbers. 

 

This was all about recursion which we will be using in Data Structures and algorithms.

 __________________________________________________________________________________

Checkout:https://javaanddsa.blogspot.com/

Did you like our blog 12??

Tell us in the comment section