How to compute the output ?

Question

How to compute the output for the recursive functions ? I know recursion invokes a stack, but am confusing while solving some aptitude question.

Given the following code snippet:

#include <stdio.h>

void fun(int a){
 if(a>0){
 fun(--a);
 printf("%d ",a);
 fun(--a);
 printf("%d ",a);
 }
return;
}

int main(void){
  int  num = 5;
  fun(num);
return 0;
}

This is not any home work assignment but I am unable to solve such question under exam condition.(Theoretical exam without Compiler)

What is the standard way to solve such question ? Please explain with a small example.Any pointer in the right direction or some web link will be welcomed.

Answer 1

Take a pen and paper; draw the invocations of the function along with the parameters - you'll have a kind of a binary tree. Track the execution and write all relevant data on the page. It will also help you understand the functionality.

The branching involved in recursive invocations (especially binary ones like this one) is very logical and intuitive when you draw it on a paper. This is how I was taught back in school - and imo its a good way of understanding stuff like this, at least at the beginning when not everything is as intuitive.

Example:

            fun [5]
          /        \
       fun[4]       fun[3]
      /      \        |    \
  fun[3]   fun[2]   fun[2]  fun[1]

I've drawn the calling tree, the same way you can draw it on the paper. This should help with making whats happening clearer for you. And that's really the way I handled this kind of stuff back in the day, so trust me - it works :)

Answer 2

This is kind of a difficult question to answer with only pen and paper, I assume it is to make sure you have understood how the computer does it, especially the two recursive calls to fun.

When simulating the execution on paper, remember that when calling fun recursively, the processor would remember the contents of local variables (here argument a) and which statement to go back to after the called function finishes.

Answer 3

You have to be the compiler and computer. Write down the stack as you go:

Enter main, call fun with 5. In fun, 5 is greater than 0, so I first decrement 5 to 4, then call fun again

Here if you are writing, I would move to the side and "start a new stack"

I enter fun with 4, which is greater than 0 I decrement 4 to 3, then call fun again

Repeat

I enter fun with 3, which is greater than 0 I decrement 3 to 2, then call fun again

Repeat again

I enter fun with 2, which is greater than 0 I decrement 2 to 1, then call fun again

And once more

I enter fun with 1, which is greater than 0 I decrement 1 to 0, then call fun again

And enter for the last time, this time

I enter fun with 0, which is not greater than 0 I return

Now you go back to where you were:

I enter fun with 1, which is greater than 0 I decrement 1 to 0, then call fun again I print out 0

On print commands, write that in yet another space, which now only contains "0". continue the function:

I enter fun with 1, which is greater than 0 I decrement 1 to 0, then call fun again I print out 0 I decrement 0 to -1 and call fun again

Here's another stack, but -1 is not greater than 0, so it does nothing. We go back into the function:

I enter fun with 1, which is greater than 0 I decrement 1 to 0, then call fun again I print out 0 I decrement 0 to -1 and call fun again I print out -1

And we finish this stack. We go back to an older stack (we just finished entering fun with 1, so look for the stack that ends with "decrement to 1 and call fun again"):

I enter fun with 2, which is greater than 0 I decrement 2 to 1, then call fun again I print out 1 I decrement 1 to 0, then call fun again

Calling fun(0) does nothing, so we return and continue:

I enter fun with 2, which is greater than 0 I decrement 2 to 1, then call fun again I print out 1 I decrement 1 to 0, then call fun again I print out 0

Then we go to the next oldest stack (we just finished entering fun with 2, so look for the stack that ends with "decrement to 2 and call fun again"):

I enter fun with 3, which is greater than 0 I decrement 3 to 2, then call fun again I print out 2 I decrement 2 to 1, then call fun again

Here's an important time saver! We've already called fun(1) once before, there's no need to really go through it again. What did fun(1) print out? Look up and you'll see it added "0-1" to the output, so save time and just append that.

This continues until you have finished. It's a lot of work, but writing down your current stacks is the easiest way to complete it. For the sake of trying to keep this already long answer short, the rest is up to you. :)

Answer 4

Add a printf("%d\n", a); at the beginning of the function (outside the if statement) and run the code to see the flow of execution. You can add another parameter to the function that takes the depth of recursion as argument and use it to indent the print statement.

The output of the following program will help you understand the flow of execution.

#include <stdio.h>

void indent(int d)
{
        for(int i = 0; i < d; i++)
                printf("\t");
}
void fun(int a, int d)
{
    indent(d);
    printf("function called with a = %d\n", a);
    if(a>0)
    {
        fun(--a, d + 1);
        indent(d);
        printf("%d\n", a);
        fun(--a, d + 1);
        indent(d);
        printf("%d\n", a);
    }
    else
    {
        indent(d);
        printf("returning as a<%d> <= 0\n", a);
    }
    return;
}

int main(void)
{
    int  num = 5;
    fun(num, 0);
    return 0;
}

Here is the output:

function called with a = 5
    function called with a = 4
     function called with a = 3
      function called with a = 2
       function called with a = 1
        function called with a = 0
        returning as a<0> <= 0
       0
        function called with a = -1
        returning as a<-1> <= 0
       -1
      1
       function called with a = 0
       returning as a<0> <= 0
      0
     2
      function called with a = 1
       function called with a = 0
       returning as a<0> <= 0
      0
       function called with a = -1
       returning as a<-1> <= 0
      -1
     1
    3
     function called with a = 2
      function called with a = 1
       function called with a = 0
       returning as a<0> <= 0
      0
       function called with a = -1
       returning as a<-1> <= 0
      -1
     1
      function called with a = 0
      returning as a<0> <= 0
     0
    2
4
    function called with a = 3
     function called with a = 2
      function called with a = 1
       function called with a = 0
       returning as a<0> <= 0
      0
       function called with a = -1
       returning as a<-1> <= 0
      -1
     1
      function called with a = 0
      returning as a<0> <= 0
     0
    2
     function called with a = 1
      function called with a = 0
      returning as a<0> <= 0
     0
      function called with a = -1
      returning as a<-1> <= 0
     -1
    1
3

Tracing recursion can be really fun. Enjoy!

Answer 5

Writing a recursive method is a bit like making a plan to line up dominoes and knock them over. You have to anticipate how each individual recursive call (domino) is going to add its part to accomplishing the whole task.

That means that the "meat" of a recursive method is not in the recursive part, but in the "end cases" the parts of the code that execute when you are not going to re-call the method, the last domino in the chain, the one that you push to start the fun.

So, let's look at your first example, a recursive program for (integer) division. The division algorithm you are trying to implement is "for positive d and n, let n(0) be n. Keep subtracting d from n(i) step by step, until in some step q, n(q) is less than d. Your answer is q."

The key is to look at the END case first. What if at the start n is already less than d? Then you did "zero steps", so your division result is 0.

In pseudocode:

int divide(int n, int d) {
if (n < d) {
return 0;
}
....
}

---

Now what if n is not less than d (greater than or equal to d)? Then we want to try another step in the division process with a smaller n. That is, run the divide function again with "the same d" and n = "the old n" - d. But once THAT divide finishes it only tells us how many subtraction steps were required for (n-d)/d. We know that n/d requires one more step. So we have to add that step tally to the result:

int divide(int n, int d) {
if (n < d) {
return 0;
} else {
return divide( n-d, d ) + 1;
}
}

---

What is that second return actually saying? It says: " I don't know how to compute the result myself, but I do know that it is ONE MORE than the result for 'divide( n-d, d )'. So I will 'pass the buck' to that method call and then just add one to whatever it gives me back."

And the process continues. We keep adding "divide" dominoes to the chain until we reach a divide operation where n has "shrunk" to be smaller than d... our end case, our zero result. Now we knock over the first domino (the last one we added to the chain), returning "0". And the dominoes begin to fall. Every time one domino knocks over another domino we add "1" to the method result until finally the first method call is the last domino to fall, and it returns the division result.

Let's try some examples:

12/18:

divide(12,18) ---> returns 0, since 12 is less than 18

result is 0.

20/5:

divide(20, 5)
---> returns divide(20-5, 5) + 1
------> returns divide(15-5, 5) +1
---------> returns divide(10-5, 5) +1
------------> returns divide(5-5, 5) +1
---------------> returns 0, since 5-5 is 0, which is less than 5
and now the dominoes fall...
------------> returns 0 + 1
---------> returns 1 + 1
------> returns 2 + 1
---> returns 3 + 1
result is 4.

---

8/3:

divide(8, 3)
---> returns divide(8-3, 3) + 1
------> returns divide(5-3, 3) +1
---------> returns 0, since 5-3 is 2, which is less than 3
and now the dominoes fall...
------> returns 0 + 1
---> returns 1 + 1
result is 2.

---