return value of the Recursive function

Question

The output of the below program is 24. But I could not understand the behaviour of the function f1(parameters).

There is a recursive call of f1 in m1 nad m2. Considering m1 and m2 holding the function f1's stack. m1 stack will contain:

1]0,12,a 2]0,6,a 3]0,3,a 4]0,1,a 5]0,0,a

And m2 stack will contain:

1]13,12,a 2]20,6,a 3]24,3,a 4]26,1,a 5]27,0,a

What m1 and m2 values hold? please explain this behaviour of the recursive function.

#include <stdio.h>
main()
{
 int i, n, m, b, x[25];
 int f1(int, int, int j[25]);
 for(i=0;i<25;i++) x[i] = i;
 i=0; m = 24;
 b=f1(i, m, x);
 printf("res %d\n",b);
}

int f1( int p, int q, int a[25])
{
 int m1,m2;
 if (q==0)
  return(a[p]);
 else
 { 
  m1 = f1 (p, q/2, a);
  m2 = f1(p+q/2+1,q/2,a);
  if(m1<m2)
   return (m2);
  else
   return(m1);
 }
}

@jv42:No this is not a homework.I could not understand how this outputs 24. — Angus
– Angus, Commented Aug 15, 2011 at 7:29
@Beata: If it's not homework, where did you get this piece of an unreadable, dirty and undocumented code? (noone with their right mind ever declares a function inside another and noone with their right mind ever calls a function f1 unless it's a quick example) — Jan Hudec
– Jan Hudec, Commented Aug 15, 2011 at 7:38
@Beata: And noone with their right mind reuses variables (i being reused after the loop) and noone with their right mind assigns constants to variables just to pass them to a function. — Jan Hudec
– Jan Hudec, Commented Aug 15, 2011 at 7:41
@Beata: So it's a homework. The "homework" tag on SO means you are trying to learn it, so good answer shall contain guidance at how to solve it rather than simply state the answer as would be appropriate if you needed to solve an urgent work problem. — Jan Hudec
– Jan Hudec, Commented Aug 15, 2011 at 7:53

Jan Hudec · Accepted Answer · 2011-08-15 08:45:29Z

Well, there are two points to understanding the code:

Uncovering the actual algorithm among the heaps of terrible C and
understanding the recursive function itself.

What always helped me when trying to understand such code was to:

Clean up the C code. In this case it means:
1. Mentally tracing the initialization and rewriting to static initialization, so you see what the values look like:
  
  int x[25] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24 };
2. Getting rid of the useless assignment to i and x so you have the initial call in plain sight.
Rewrite the function to mathematical notation, pseudocode or even human laguage.
```
f(p, q, array) = larger of f(p, q/2, array) and f(p+q/2+1, q/2, array)
```
if you continue a little bit further in using human language, you'll clearly see what is was supposed to do.

Now I said "was supposed to do" on purpose. The (p, q/2) and (p+q/2+1, q/2) look like the first and second half... except they are not.

The code is supposed to return 24, but it's totally wrong and the stacks quoted in the question actually prove it. The m2 stack contains as last point "f1(27, 0, a)" and that invocation is going to do a[27], but the array only has 25 elements! (by pure chance the memory above was probably 0-initialized, so it did return the 24, but if it was initialized by some debug pattern instead (I've seen 0xdeadbeef, 0xa5a5a5a5 and 0xcccccccc), it would return that).

In C it's by design (and C++ uses them everywhere) easiest to use half-open intervals. [start, one-past-end) or start+length, which convert to each other nicely. However here the function gets (start, length-1) and treats it inconsistently inside.

As a student, you have to be able to understand such code, because you'll meet lots of crappy unreadable bug ridden code that only works by accident in the wild. But if you ever present something like this, you will rightfully fail the exam.

djna · Accepted Answer · 2011-08-15 07:33:47Z

2

Here you can't think of an m1 stack and an m2 stack as non-terminating calls to f1 result in an m1 and an m2 recursive call.

To analyze what's happening try it for a small value of p and q.

   f1( 0, 1, a)
      m1 = f1( 0, 0, a); /* q/2 == 1/2 == 0 */
           /* q now 0 so return a[0] */
      m2 = f1( 1, 0, a);
           /* q now 0 so return a[1] */ 

   overall result the larger of a[0] and a[1].

Now try it for f1( 0, 2, a) and so on, till you see what's happening.

answered Aug 15, 2011 at 7:33

djna

56.2k14 gold badges80 silver badges125 bronze badges

Collectives™ on Stack Overflow

return value of the Recursive function

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related