GATE2025_CS1_Q61

The value printed by the given C program is _______. (Answer in integer)

#include int foo(int S[],int size) { if(size == 0) return 0; if(size == 1) return 1; if(S[0] != S[1]) return 1+foo(S+1,size-1); return foo(S+1,size-1); } int main(){ int A[]={0,1,2,2,2,0,0,1,1}; printf("%d",foo(A,9)); return 0; }

✅ Final Answer:

The correct answer is 5.

🔹 Short Answer:

The recursive function foo effectively counts the number of "groups" of identical consecutive elements in the array. It does this by adding 1 to the result only when two adjacent elements are different. For the array {0, 1, 2, 2, 2, 0, 0, 1, 1}, the groups are (0), (1), (2,2,2), (0,0), and (1,1). There are 5 such groups, so the function returns 5.

🔸 Long Answer:

This question requires a careful trace of a recursive C function that uses pointer arithmetic on an array.

Function Analysis

The function foo(int S[], int size) does the following:

• Base Cases: If the array slice is empty (size == 0), it returns 0. If it has only one element (size == 1), it returns 1.
• Recursive Step 1: It checks if the first two elements of the current array slice, S[0] and S[1], are different. If they are, it adds 1 to the result of a recursive call on the rest of the array.
• Recursive Step 2: If the first two elements are the same, it makes a recursive call on the rest of the array without adding 1.
• Pointer Arithmetic: The term S+1 passes a pointer to the second element of the current array slice, effectively processing the array from left to right.

Step-by-step Execution Trace

Let's trace the execution of foo(A, 9) where A = {0,1,2,2,2,0,0,1,1}.

• foo({0,1,2,2,2,0,0,1,1}, 9): 0 != 1. Returns 1 + foo({1,2,...}, 8)
• foo({1,2,2,2,0,0,1,1}, 8): 1 != 2. Returns 1 + foo({2,2,...}, 7)
• foo({2,2,2,0,0,1,1}, 7): 2 == 2. Returns foo({2,2,...}, 6)
• foo({2,2,0,0,1,1}, 6): 2 == 2. Returns foo({2,0,...}, 5)
• foo({2,0,0,1,1}, 5): 2 != 0. Returns 1 + foo({0,0,...}, 4)
• foo({0,0,1,1}, 4): 0 == 0. Returns foo({0,1,...}, 3)
• foo({0,1,1}, 3): 0 != 1. Returns 1 + foo({1,1}, 2)
• foo({1,1}, 2): 1 == 1. Returns foo({1}, 1)
• foo({1}, 1): size == 1. Returns 1.
• Result is 1. Returns 1.
• Result is 1 + 1. Returns 2.
• Result is 2. Returns 2.
• Result is 1 + 2. Returns 3.
• Result is 3. Returns 3.
• Result is 3. Returns 3.
• Result is 1 + 3. Returns 4.
• Result is 1 + 4. Returns 5.

The final value returned to main and printed is 5.

Bibliography:
- Kernighan, B. W., & Ritchie, D. M. (1988). The C Programming Language. Prentice Hall. (Chapter 5: Pointers and Arrays).
- Prata, S. (2014). C Primer Plus. Addison-Wesley Professional. (Chapter 10: Arrays and Pointers).

Ask your doubts in comment form our GURUJEE will reply ASAP, click notify me button so that you get notified on reply.