GATE CS 2016 Set 2 Q.47 (CS Q.37): Functions, Recursion, Scope and Storage Classes

Consider the following program:

int f(int *p, int n)
{
    if (n <= 1) return 0;
    else return max(f(p+1,n-1),p[0]-p[1]);
}
int main()
{
    int a[] = {3,5,2,6,4};
    printf("%d", f(a,5));
}

Note: max(x,y) returns the maximum of x and y.

The value printed by this program is ________.

Your answer

Official answer and solution

Official answer: 3
From: Official GATE 2016 answer key

Solution

Trace the recursive execution of the function to see that it computes the maximum difference between any two adjacent elements.

The recursive function is defined as:

int f(int *p, int n) {
    if (n <= 1) return 0;
    else return max(f(p+1, n-1), p[0] - p[1]);
}

Unrolling the recursion for an array of size $n$ :

f(p, n) = \max\left(p[0] - p[1], p[1] - p[2], \dots, p[n-2] - p[n-1], 0\right)

It computes the maximum adjacent difference $a[i] - a[i+1]$ across the array, bounded below by 0.

Given array $a = \{3, 5, 2, 6, 4\}$ of size 5:

$i = 0$ : $a[0] - a[1] = 3 - 5 = -2$
$i = 1$ : $a[1] - a[2] = 5 - 2 = 3$
$i = 2$ : $a[2] - a[3] = 2 - 6 = -4$
$i = 3$ : $a[3] - a[4] = 6 - 4 = 2$

Evaluate the maximum:

\max(-2, 3, -4, 2, 0) = 3

Therefore, the value printed by the program is 3.

Final answer

Common trap

Confusing adjacent difference $a[i] - a[i+1]$ with absolute difference or with maximum element in the array.

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Source

Paper: GATE 2016 Computer Science and Information Technology (CS) Session 2
Question: 47 of 65, printed as CS Q.37
Section: Computer Science and Information Technology

Report an error in this question

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.

Question

Solution

Source