Solving this identify function?

Question

Consider the following C function definition
int Trial (int a, int b, int c)
{
    if ((a>=b) && (c< b)) return b;

    else if (a>=b) return Trial(a, c, b);

    else return Trial(b, a, c);
}
The functional Trial:

a) Finds the maximum of a , b , and c

b) Finds the minimum of a , b , and c

c) Finds the middle number of a , b , c

d) None of the above

======================================================================

My take - I took a = 1 b= 2 c = 3 and got answer as 2 which is middle element, but that's wrong answer and correct answer is option (d)

So, where am I going wrong?

Why don't you single step through the code with your debugger and see for yourself? Writing recursive goo like this holds no purpose. If anything, it just teaches you how to write unreadable and ineffective programs. — Lundin, Jun 26 '18 at 06:38
@Lundin This has been asked in an objective exam where they're asking for the final answer and all I've provided with is a PEN AND PAPER and no computer at all in the exam — Geeklovenerds, Jun 26 '18 at 06:39
Pencil & paper works just as well as a debugger from stepping through code. Just set up a "Truth Table". — David C. Rankin, Jun 26 '18 at 06:41
"The program returns 2 when the input is 1, 2, 3" does not entail "The program returns the median of three numbers for all inputs". — n. m. could be an AI, Jun 26 '18 at 06:44
@Geeklovenerds Yeah so what? Go run the code in your debugger. Or are you posting this question while taking the exam? — Lundin, Jun 26 '18 at 06:46
@Lundin No, I'm at not any exam and I did run it and it gives 2 as answer for a = 1 b = 2 c = 3, but how can one be sure in exam that it has to check for a = b = c = 1 — Geeklovenerds, Jun 26 '18 at 07:16

score 4 · Answer 1 · answered Jun 26 '18 at 06:44

4

This function would cause a stack overflow due to infinite recursion in the case where a=b=c, eg:(1,1,1). Considering all edge cases would be integral in getting to the solution in MCQs like this one.

answered Jun 26 '18 at 06:44

deadlock

103
1
6

or for `a = b` and `a <= c`. – Stargateur Jun 26 '18 at 06:45
Not necessarily stack overflow; it may just never terminate. – melpomene Jun 26 '18 at 06:48
@melpomene which will cause a stackoverflow, because everytime the function calls itself it adds information on the stack, which is not infinite – Martin Verjans Jun 26 '18 at 06:51
@MartinVerjans Function calls don't necessarily use stack space. – melpomene Jun 26 '18 at 06:52
1

@MartinVerjans Here's a practical demonstration: https://godbolt.org/g/iPxoMs. Note how there are no `call` instructions there. – melpomene Jun 26 '18 at 06:56
@deadlock how to be sure in exam, that I take different values? If I take a = 1 b= 2 c = 3 then I get answer c) and I'll tick that which apparently is wrong! – Geeklovenerds Jun 26 '18 at 07:15
@melpomene My mistake you're right. I thought the function call would always generate a call. Did learn something today. – Martin Verjans Jun 26 '18 at 07:27
1

@Geeklovenerds practice is what I could suggest. MCQs are sometimes intended to trick you, and in this case, I'd say the condition (a>=b) rather than an innocent (a>b) is what would lead me to consider more than just a simple case where a=b) as well, you'd want to use more cases to your solution, like a=bc and probably a=b=c as well. – deadlock Jun 26 '18 at 08:00

Bathsheba · Answer 2 · 2018-06-26T06:57:54.880

1

Prior to C11, the behaviour of the code is undefined for the case where a, b, and c are all equal. (All other cases can be checked trivially with a debugger or old-fashioned pen and paper analysis.)

This is because in that situation the code calls itself ad infinitum. And an infinite loop with no input or output was undefined in C up to but not including C11.

In my opinion the extra clauses added to C11 in an attempt to define this add extra confusion in this case. See Is while(1); undefined behavior in C?

I believe the compiler can (theoretically) optimise the program to tail recursion; so obviating any implementation issues around stack overflows, for example. It could do that quite trivially if the program is recast to

int Trial (int a, int b, int c)
{
    if (a >= b && c < b) return b;
    return Trial(a >= b ? a : b, a >= b ? c : a, a >= b ? b : c);
}

edited Jun 26 '18 at 06:57

answered Jun 26 '18 at 06:52

Bathsheba

231,907
34
361
483

1

`gcc -O2` compiles the original function to a simple loop. – melpomene Jun 26 '18 at 07:01
@melpomene Wow. gcc always pops out as being cleverer than I think. I didn't think it would spot the tail recursion without the rewriting as above. – Bathsheba Jun 26 '18 at 07:02
Nah, that one's easy. All the recursive calls are direct operands of `return`. But check this one out: https://godbolt.org/g/tNos77 (not tail recursion, still turns into a loop). – melpomene Jun 26 '18 at 07:08

score 1 · Accepted Answer · answered Jun 26 '18 at 07:12

1

This code will give StackOverflowError for following a,b,c values (1,2,1) , (1,1,2) , (2,1,1) , (2,2,2) For any number in above pattern eg (1,2,1) a==c and b >a and b >c , this will throws error.

As you mention for input 1,2,3 you get value 2 as output. So Option A "maximum" and B"minimum" is wrong. Option 3 seems to be correct for inputs but code will not work for pattern of inputs mentioned above. So correct answer should be option "D" Non of the above.

answered Jun 26 '18 at 07:12

Dharmendra Rathor

77
1
5

how to be sure in exam, that I take different values? If I take a = 1 b= 2 c = 3 then I get answer c) and I'll tick that which apparently is wrong! – Geeklovenerds Jun 26 '18 at 07:15
It is good to run code with different types of inputs. eg : a>b>c (1,2,3) , a=b=c (2,2,2), other inputs like 1,2,1 . before we finalize the result . Second input in this case would have given stack over flow error. – Dharmendra Rathor Jun 26 '18 at 07:27

Solving this identify function?

3 Answers3