Recursion — Guess the outputs

Source: MemeZila

So here we go. Since we have now learnt the basics in the previous article, let’s do the hands on by guessing the outputs.

Below given is a pseudo code of a recursive function. It is not specific to any language. Read it and don’t scroll the page until you process it and write some output. Grab a paper and a pen and start drawing the function calls. It will give you an accurate idea of what the output will be.

This is the second article of recursion series. Read the complete series list here with articles in order: https://medium.com/the-ds-man/a-series-on-recursion-478aa3d3d88

Code 1

Guess the output of pseudo code below:

The output will be 321123. How that came ? Let’s make a diagram of function execution like we did in the previous article.

As the main function calls fun(3), it first executes the print statement and prints 3 as output. Then the control moves to next statement where the function is calling itself with value n-1. So, it calls fun(2) and when fun(2) gets executed, it prints again the value of n which is 2. Now, control does the function keeps calling itself until the value of n reaches to 0. That’s the point where our base case gets executed and if condition becomes true. At that point, the fun(0) immediately returns and ends the execution of itself. Now for fun(1), fun(n-1) is completed. So, the control moves to next line where the print(n) statement is there. So, it prints 1 again and the execution of fun(1) is now completed. Similar thing happens for fun(2) and 2 gets printed and then 3. So the output becomes 321123.

Code 2

Guess the output of pseudo code below:

The output will be 1213121. Let’s again make a diagram of function execution.

Pheww!! That looks overwhelming. If you have already figured this out, you are awesome. If not, its OK. Let’s take a look at the explanation. I have made it in steps, so that it can be easier to understand.

1. The execution starts with fun(3).
2. fun(3) calls fun(2) and wait for its execution to get completed.
3. fun(2) calls fun(1) and wait for its execution to get completed.
4. fun(1) calls fun(0). Not at this point, our base case condition becomes true and fun(0) returns immediately.
5. Now, we are at fun(1) execution. Take a look at the code. We have now a print statement which prints the current value of n. So, 1 is printed.
6. In the next step, fun(1) again calls fun(0) which returns immediately.
7. At this point, our fun(1) execution is completed and we are at fun(2) now as shown in diagram.
8. fun(2) now prints the value of n which is 2. And it again calls fun(1).
9. Now, steps 4 to 6 gets repeated and 1 is printed again.
10. Now, fun(2) is completed and we are back to fun(3).
11. The print statement at fun(3) gets executed and prints 3.
12. It then again calls for fun(2) and the whole steps from 3 to 10 gets repeated.

That’s all for this example. If you take a pen and paper and draw diagrams, it will always be easy to understand how the function is working and what is the output it will produce.

Beep Boop. Boop Beep. Sorry to interrupt. But we are building a very large developer community on Discord with thousands of developers from all around the world with all levels. We are just started out and hoping to make it big.

This Discord server will have all the knowledge you will ever need to become a great programmer. You will learn about technologies you have never heard of. There will be projects for all levels, jobs posting, conferences, events and a lot more. We will also post daily problems on it, so that you can stay on the top on problem solving.

There will be lots of tutorials, live coding etc. I would request to kindly join and make yourself the part of biggest developer community. It’s a start and it will eventually grow. It’s a request not to leave it after joining if there’s not much engaging content at that point of time. But, we are working round the clock to make it happen.

Please join here: https://discord.gg/kzE8kBvCyG

Code 3

Guess the output of pseudo code below:

The output will be 4. If you guessed it right, it’s awesome. If not, let’s see the diagram on the execution of this function:

Click to view

Seems interesting na. It’s simple. We will again take that steps explanation approach as it is clear and easy to understand. So, here are the steps:

1. We call fun(16) from main and the execution of this function begins.
2. First the base case if condition is checked which is obviously not true. So the control moves to the return statement which returns 1 + fun(8).
3. So control will start executing fun(8). This function also returns 1 + fun(4).
4. This process will go on until fun(1) is called and base case is reached.
5. At this point the function returns 0 and the value of 1 + fun(1) is returned as 1.
6. Now the value will keep on returning at every return statements throughout the call stack and at the end, we will get our final answer 4 returned.

Did you see an interesting pattern in this program ? Can you think of something what this function is doing mathematically ? Let’s find out.

Let’s put some more function calls and see the output.

1. fun(1) = 0
2. fun(2)= 1 + fun(1) = 1
3. fun(4)= 1 + fun(2) = 2
4. fun(8) = 1 + fun(4) = 3
5. fun(16) = 1 + fun(8) = 4

When we multiply our input by 2, our result gets incremented by 1. This is how log works mathematically. So for the above, it will be log n with the base 2. This expects that n is the power of 2. How about the inputs where n is not a power of 2. Let’s find out. In below outputs, when we do integer division by two, the executor always ignores the remainders. So, it will always return the ceil value.

1. fun(17) = 1 + fun(8) = 4 = fun(16)
2. fun(18)= 1 + fun(9) = 1 + 1 + fun(4) = 1 + fun(8) = 4 = fun(16)
3. fun(19)= 1 + fun(9) = 1 + 1 + fun(4) = 1 + fun(8) = 4 = fun(16)
4. fun(20)= 1 + fun(10) = 1 + 1 + fun(5) = 1 + 1 + 1 + fun(2) = 4 = fun(16)

So the pattern here is, if you keep increasing the value of n until the next power of 2, it will give you floor log n. Try finding the return value of fun(31) and fun(32). You will get the same answer for fun(31) and the value will increase for fun(32) since it is the next power of 2.

If we want to get the output as floor of log to the base 3. Can you think how you have to modify the code and make it happen ? The solution is, just divide the function calls in return statements by 3 rather than 2 and change the base case from equal to 1 to less than 3. That’s all.

Code 4

Guess the output of the pseudo code below and think about what this function is doing in general.

The output will be 111. This was the easy one right. Hope at this point, you were able to answer correctly. If not, don’t worry. We have a lot of problems and exercises to make you feel powerful in recursion. Let’s take a look at the execution diagram.

Let’s look at the steps:

1. When we call fun(7), the first statement is to check the base case which is false.
2. The control moves to a function call fun(3). Since, it is the integer division, only floor will be considered and remainder will be ignored.
3. fun(3) will call fun(1) which in turn calls fun(0) and at this point, the base case is reached.
4. So, executing the print statement, 1 % 2 prints 1.
5. Then 3 % 2 prints 1 and then 7 % 2 prints 1.

That’s all. If you haven’t figured it out yet what this function is doing in general, find a solution of method call fun(13) and write the output.

I think now you got it. Yes, it’s giving us the binary of decimal numbers. See, you unknowingly now know how to convert decimal to binary using recursion.

Read further

This was the second article of recursion series. You can find the list of complete recursion series here: https://medium.com/the-ds-man/a-series-on-recursion-478aa3d3d88

That’s all Folks !!!