Print Zig Zag using recursion

Written By Ritik Kaushik

Print Zig Zag Using Recursion

Input1 -> 1

Output1 -> 1 1 1

Input2 -> 2

Output2 -> 2 1 1 1 2 1 1 1 2

Input2 -> 3

Output3 -> 3 2 1 1 1 2 1 1 1 2 3 2 1 1 1 2 1 1 1 2 3

Figure out the pattern and print the output for any positive number n.

Solution:

The code for this question is fairly simple, but the main purpose of this question is to understand how recursion works behind the scenes and how the recursive code flows.

public static void pzz(int n){

if(n==0){

return;

}

System.out.print(n+” “);

pzz(n-1);

System.out.print(n+ ” “);

pzz(n-1);

System.out.print(n+ ” “);

}

This article can be very long so I need focus and patience from you guys. Believe me, if you spend some time on this article, you will become a master of recursion.

I hope you guys know that stack is used to execute the recursion code internally. If you don’t know then it’s okay, we will cover everything in this article. Let me show you how by taking a simple recursion example:

public static void print(int n){

if(n==0){

return;

}

print(n-1);

System.out.println(n + ” “);

}

The output of the above code for input 4 would be 1 2 3 4

Now we’ll see how the above code executes inside your machine.

But before proceeding I want you to keep in mind the following points. Don’t panic if you are unable to understand the below points, you will definitely understand them when I walk you through an example. I just want you to read the points once or twice.

1. At any point in time, only the function that is at the top of the stack will execute its code.
2. The function will get popped out of the stack only if it has finished its execution completely. It means when all the lines of code of a function have finished then it will be popped out of the stack or if we encounter a  return keyword then also the function will be popped out of the stack.
3. Stack also keeps track of how many lines of code of each function has been executed. This point makes more sense when you understood the 2nd point.

So let’s start:-

public static void print(int n){

if(n==0){ //Line no. 1

return; //Line no. 2

} //Line no. 3

print(n-1); //Line no. 4

System.out.println(n + ” “); //Line no. 5

}

We will execute this code line by line for input 4. Initially, our stack is empty, then we call print(4) so now print(4) is pushed onto the top of the stack. I hope you understood how recursive code executes inside the computer. Now, I want you guys to grab a notebook and draw the stack state diagram for the original code of this question.

Remember to keep track of how many lines has been executed for each function, I think now you know when to push a function to stack? (when you encounter a line with a recursive call), when to pop a function from a stack? (when all the lines of code for that function has finished or when you encounter a return keyword), Remember only the function which is at the top will execute its code.

If you are unable to draw, don’t worry I will explain but it is important to first try on your own.

public static void pzz(int n){

if(n==0){ //Line 1

return; //Line 2

} //Line 3

System.out.print(n+” “); //Line 4

pzz(n-1); //Line 5

System.out.print(n+ ” “); //Line 6

pzz(n-1); //Line 7

System.out.print(n+ ” “); //Line 8

}

I will explain it for small input n=1, If you don’t understand it, then I recommend you to watch Sumeet sir’s video for this question from 3:00  https://youtu.be/R7qja_gZrvI?t=183

This is how recursive code executes inside the computer. But don’t you think this method is very lengthy. It would be very hard to draw diagrams for large inputs n=6 or 7.

There is another method which we call as a recursion tree or Euler tree

In our code, there are two calls to pzz(n-1). One is on line no. 5 and another is on line no. 7 . We will say first call as left call and second call as right call.

All the code before left call is known as Pre Region.

All the code between left call and right call is known as In Region.

All the code after the right call is known as Post Region. So guys, what is happening:-

1. First of all pre-region code of “2” will execute after that that left call to “1” will be made

2. pre-region code of “1” will execute then left call is made to “0”

3. For “0” in the pre-region itself return keyword is encountered so, neither left nor right call

4. Control will again go to “1”, now the code in in-Region of “1” will execute and right call

5. For “0” in the pre-region itself return keyword is encountered so, neither left not right call

6. Control will again go to “1”, now the code in post-region of “1” will execute.

7. Now all the regions of “1” has executed so the control gain goes to “2”

8. Now, the in-region code of “2” will execute and a right call is made to “1”

9. pre-region code of “1” will execute then left call is made to “0”

10. For “0” in the pre-region itself return keyword is encountered so, neither left nor right call

11. Control will again go to “1”, now the code in in-Region of “1” will execute and right call

12. For “0” in the pre-region itself return keyword is encountered so, neither left not right call