CODEWITHSUNDEEP
cgcc
Rajan Chennai
Rajan Chennai

Reputation: 145

Needed a solution on recursive function

#include <stdio.h>

void call(int n )
{
    if ( n > 0 )
    {
        call(--n) ;
        printf("\n%d",n) ;
        call(--n) ;
    }
}

int main(void )
{
    int a = 3 ;
    call(a) ;
    return 0 ;
}

In the above mentioned code i am having a difficulty to understand the logic behind it. I am getting 0 1 2 0 as the output. Why?

Upvotes: 2

Views: 140

Answers (3)

Will Ness
Will Ness

Reputation: 71065

First, find your base case: call(n), when n<=0 does nothing and just returns.

In the general case for code(n) the definition says: "decrement n and recurse (all the way down); when the control is back, print n (its value is preserved), decrement again and recurse again".

Or, with equations:

call(n) | when(n<=0) = NO-OP
call(n) | otherwise  = call(n-1), print(n-1), call(n-2)

So, 

call(1) = call(0), print(0), call(-1)
        = print(0)

call(2) = call(1), print(1), call(0)
        = print(0), print(1)

call(3) = call(2), print(2), call(1)
        = (print(0), print(1)), print(2), print(0)

Continuing,

call(4) = 0120+3+01
call(5) = 0120301+4+0120
call(6) = 012030140120+5+0120301
....

It seems we can generate the indefinite sequence of resulting outputs, maintaining just the two most recent values:

(n,a,b) --> (n+1,b,b+n+a)

So instead of recursion down towards the base case, this describes corecursion up away from the starting case, (2,0,1) (the 1 case is covered by a special fact (1,_,0)). We can code it as an actual indefinitely growing (i.e. "infinite") sequence, or we can just make an infinite loop out of it.

What would be the purpose of such non-terminating computations? To describe the computation of the results, in general. But of course it is extremely easy to cut short such computation when we reach a target value for n.

The benefit? Instead of recursion, we get an iterative loop!

output(1) = "0"
output(n) | when(n>1) = 
   let {i = 2, a="0", b="1"}
   while( i<n ):
      i,a,b = (i+1),b,(b+"i"+a)
   return b

Upvotes: 5

Anthill
Anthill

Reputation: 1249

When trying to understand code flow I can't wrap my head against I use a simple strategy:

log the output in a detailed manner. For instance, instead of having a simple printf statement in your call function you can map the flow of the application. Here's an example

#include <stdio.h>

void call(int n, int depth)
{
    printf("%.*s(enter) n is (%d)\n", ++depth, "-----", n);
    if ( n > 0 )
    {
        call(--n, depth) ;

        call(--n, depth) ;
    }
    printf("%.*s(exit) n is (%d)\n", depth--, "-----", n);
}

int main(void )
{

    int a = 3 ;

    call(a, 0) ;
    getchar();
    return 0 ;
}

This will result in:

-(enter) n is (3)
--(enter) n is (2)
---(enter) n is (1)
----(enter) n is (0)
----(exit) n is (0)
----(enter) n is (-1)
----(exit) n is (-1)
---(exit) n is (-1)
---(enter) n is (0)
---(exit) n is (0)
--(exit) n is (0)
--(enter) n is (1)
---(enter) n is (0)
---(exit) n is (0)
---(enter) n is (-1)
---(exit) n is (-1)
--(exit) n is (-1)
-(exit) n is (1)

Upvotes: 1

John Kugelman
John Kugelman

Reputation: 361585

call(3)
│ n3=3
│ --n3 (n3=2)
├╴call(2)
│ │ n2=2
│ │ --n2 (n2=1)
│ ├╴call(1)
│ │ │ n1=1
│ │ │ --n1 (n1=0)
│ │ ├╴call(0)
│ │ │ └ return
│ │ │
│ │ │ printf("\n0");           ⇦ 0
│ │ │
│ │ │ --n1 (n1=-1)
│ │ ├╴call(-1)
│ │ │ └ return
│ │ └ return
│ │
│ │ printf("\n1")              ⇦ 1
│ │
│ │ --n2 (n2=0)
│ ├╴call(0)
│ │ └ return
│ └ return
│
│ printf("\n2");               ⇦ 2
│
│ --n3 (n3=1)
├╴call(1)
│ │ n1=1
│ │ --n1 (n2=0)
│ ├╴call(0)
│ │ └ return
│ │
│ │ printf("\n0");             ⇦ 0
│ │
│ │ --n1 (n1=-1)
│ ├╴call(-1)
│ │ └ return
│ └ return
└ return

Upvotes: 5

Related Questions