GATE CS Recursion Previous Year Questions

GATE CS 2025 Set 1 | Question 61

NAT · 2 marks

#include <stdio.h>
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;
}

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

Your answer

Explanation

Answer: 5

Each call compares the first two elements and then moves one place to the right. It adds 1 whenever the two neighbours differ, and the last single element adds 1 more (the size 1 case). So foo returns the number of unequal neighbour pairs plus 1, which is the number of runs of equal values.

In 0, 1, 2, 2, 2, 0, 0, 1, 1 there are 4 unequal pairs: (0, 1), (1, 2), (2, 0) and (0, 1). They split the array into the runs 0 | 1 | 2 2 2 | 0 0 | 1 1.

Value printed \(= 4 + 1 = 5\).

Answer: 5

GATE CS 2024 Set 1 | Question 19

MCQ · 1 mark · −0.33

Consider the following C program:

#include <stdio.h>
void fX();
int main(){
   fX();
   return 0;}

void fX(){
 char a;
 if((a=getchar()) != '\n')
     fX();
 if(a != '\n')
     putchar(a);}

Assume that the input to the program from the command line is 1234 followed by a newline character. Which one of the following statements is CORRECT?

The program will not terminate The program will terminate with no output The program will terminate with 4321 as output The program will terminate with 1234 as output

Explanation

Answer: (C)

Each call of fX reads one character into its own local variable a. If that character is not a newline, the call recurses first and prints its own character only after the inner call returns, so characters come out in the reverse of the order they were read.

With the input 1234 and a newline, five nested calls read '1', '2', '3', '4' and '\n'. The fifth call neither recurses nor prints, and returns. The waiting calls then print 4, 3, 2 and 1 as they unwind, and main returns.

The newline ends the recursion, so the program terminates (not A) and prints 4321. Printing 1234 would need putchar before the recursive call.

Answer: C