Recursion and Recursive Program Analysis PYQs for GATE CS

Solve 6+ Recursion and Recursive Program Analysis previous year questions for GATE CS with answers and detailed solutions. Free sample questions below.

Boundary and Scope of Recursive Traversal

This specification defines the boundary of recursive traversal. We restrict our focus to linear structures. You will analyze how a function reduces an array or transforms a string by delegating the remainder of the structure to a subsequent call.

The anchor for our analysis is an array of eight integers containing four contiguous blocks of identical values: [4, 4, 1, 1, 1, 7, 2, 2]. We will use this structure to isolate the mechanics of state accumulation and deferred execution.

Explain this more simply

Think of a conveyor belt moving boxes past a scanner. The scanner processes the current box, then signals the next section of the belt to move the remaining boxes. Recursive traversal operates identically: the function processes the current element, then delegates the rest of the array to the next recursive call.

Go one level deeper

Linear recursion is strictly bounded by the size of the input. Unlike tree or graph recursion, there is only one recursive call per invocation. This guarantees that the recursion depth is exactly N, making the call stack predictable and the execution path a single, unbranching line of descent followed by a single line of ascent.

Pointer Arithmetic in Recursive Steps

When passing an array to a recursive call, the standard mechanism is pointer arithmetic. If S is a pointer to the first element of an integer array, the expression S+1 does not add one to the value of the first element. It advances the memory address by the size of one integer.

Consequently, the recursive call f(S+1, size-1) shifts the view of the array forward by one element while reducing the tracked size. This is the recursive equivalent of incrementing an index in an iterative loop.

S[0]

S[1]

S[2]

S[3]

S+1 moves the pointer to the second box. The data inside the boxes does not change.

Explain this more simply

Imagine a row of mailboxes. S points to mailbox 0. S+1 does not change the mail inside mailbox 0; it simply moves your physical position to point at mailbox 1. The recursive function is just a person walking down the row, looking at one mailbox at a time.

Go one level deeper

Misinterpreting this shift as value addition is a primary source of error. In C, S+1 relies on the base type of the pointer. If S is a char pointer, S+1 advances by one byte. If S is an int pointer, it advances by four bytes. The compiler handles the scaling, but the programmer must understand that the array view shifts, not the underlying data.

Recursion and Recursive Program Analysis: Solved Questions with Step-by-Step Explanations (6 Problems)

Question 1 · Programming and Data Structures · 2026_Set2 NAT

Consider the following ANSI-C function.

int func(int start, int end){
              int length=end+1-start;
              if((length<1)||(start<0)||(end<0)){ return(0); }
              if(length%3==0){
                        return(func(start+1, end));
              } else if(length%3==1){
                        return(1+func(start, end-1));
              } else {
                        return(func(start+2, end));
              }
}

The maximum possible value that can be returned from this function is ____________. (answer in integer)

Note: Ignore syntax errors (if any) in the function.

Correct Answer:

1.00

Step-by-Step Solution

Insight: The function's return value depends on length % 3. The only branch that adds 1 is length % 3 == 1, which transitions the length to length - 1 (residue 0). From residue 0, the sequence of residues is 0 -> 2 -> 0 -> 2..., never returning to 1. Thus, 1 is added at most once.

Exam route: Let $L$ be the initial length.

If $L \equiv 1 (mod 3)$ : adds 1, new $L \equiv 0 (mod 3)$ .

If $L \equiv 0 (mod 3)$ : adds 0, new $L \equiv 2 (mod 3)$ .

If $L \equiv 2 (mod 3)$ : adds 0, new $L \equiv 0 (mod 3)$ .

The residue 1 is visited at most once. The maximum return value is 1, achievable when $L = 1$ .

Learning route:

This is a modulo state-transition recursion question, recognisable because the branch taken and the amount subtracted from the effective length depend on length % 3.
Define $L = end + 1 - start$ . The base case returns 0 if $L < 1$ or if an index is negative.
Determine how each branch changes $L$ :

If $L \equiv 0 (mod 3)$ , the call is func(start+1, end), so new length is $L - 1$ .
If $L \equiv 1 (mod 3)$ , the return is $1 +$ func(start, end-1), so new length is $L - 1$ .
If $L \equiv 2 (mod 3)$ , the call is func(start+2, end), so new length is $L - 2$ .

Convert to residue transitions:

$L \equiv 1 \Rightarrow add 1, L \to L - 1 \equiv 0,$

$L \equiv 0 \Rightarrow add 0, L \to L - 1 \equiv 2,$

$L \equiv 2 \Rightarrow add 0, L \to L - 2 \equiv 0.$

The only adding state is residue 1. If the computation starts in residue 1, it adds once and moves to residue 0. From residue 0, it moves to 2, then back to 0, never visiting 1 again.
Thus, the maximum possible value is 1.

Tempting wrong path: assume the residue cycle allows multiple additions of 1. This breaks because the cycle $0 \to 2 \to 0$ never includes residue 1, so the addition stops after the first step.

Verification: For start = 0, end = 0, $L = 1$ . $1 \equiv 1 (mod 3)$ , returns $1 + func (0, - 1)$ . $func (0, - 1)$ has $L = 0 < 1$ , returns 0. Total = 1.

Question 2 · Programming and Data Structures · 2026_Set1 NAT

Consider the recursive functions represented by the following code segment:

int bar(int n){
  if (n == 1) return 0;
  else return 1 + bar(n/2);
}

int foo(int n){
  if (n == 1) return 1;
  else return 1 + foo(bar(n));
}

The smallest positive integer n for which foo(n) returns 5 is ______. (answer in integer)

Note: Ignore syntax errors (if any) in the function.

Correct Answer:

65536.00

Step-by-Step Solution

Insight: bar(n) computes $⌊ lo g_{2} n ⌋$ , and foo(n) counts how many times bar must be applied to reach 1. Work backwards from the base case using the smallest preimage at each step.

Exam route: foo(1) = 1. To get foo(n) = 5, we need 4 recursive steps. The inverse of bar(x) = k with the smallest x is $x = 2^{k}$ .

Step 1: foo(x_4) = 1 \implies x_4 = 1.

Step 2: bar(x_3) = 1 \implies x_3 = 2^1 = 2.

Step 3: bar(x_2) = 2 \implies x_2 = 2^2 = 4.

Step 4: bar(x_1) = 4 \implies x_1 = 2^4 = 16.

Step 5: bar(n) = 16 \implies n = 2^{16} = 65536.

Learning route:

This is a nested recursion question, recognisable because foo calls bar inside its recursive step.
Analyse bar(n): it adds 1 and halves n until n=1. This is the definition of $⌊ lo g_{2} n ⌋$ .
Analyse foo(n): it adds 1 and replaces n with bar(n) until n=1. The base case foo(1) = 1 means the total sum is $1 + number of steps$ .
We want foo(n) = 5, so we need exactly 4 steps to reach 1.
To find the smallest n, we must choose the smallest preimage at each step. Since bar(x) = k means $2^{k} \leq x < 2^{k + 1}$ , the smallest x is $2^{k}$ .
Working backwards: $x_{4} = 1 ⟹ x_{3} = 2^{1} = 2 ⟹ x_{2} = 2^{2} = 4 ⟹ x_{1} = 2^{4} = 16 ⟹ n = 2^{16} = 65536$ .

Tempting wrong path: Count 5 reductions instead of 4. This breaks because the base case foo(1)=1 already provides 1, so only 4 reductions are needed to reach 5. This would lead to $2^{32}$ , which is incorrect.

Verification: bar(65536) = 16, bar(16) = 4, bar(4) = 2, bar(2) = 1. foo(65536) = 1 + foo(16) = 2 + foo(4) = 3 + foo(2) = 4 + foo(1) = 5. Correct.

Question 3 · Programming and Data Structures · 2025_Set1 NAT

#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)

Correct Answer:

5.00

Step-by-Step Solution

Insight: The function counts the number of contiguous blocks (runs) of identical elements. It adds 1 whenever adjacent elements differ, and the base case size == 1 adds the final 1 for the last run.

Exam route: Array is 0, 1, 2, 2, 2, 0, 0, 1, 1.

Adjacent differences:

0!=1 (1), 1!=2 (1), 2==2 (0), 2==2 (0), 2!=0 (1), 0==0 (0), 0!=1 (1), 1==1 (0).

Total differences = 4.

Add 1 for the base case: 4 + 1 = 5.

Learning route:

This is a recursive array traversal question, recognisable because the function compares the first two elements and then recurses on the tail using S+1 and size-1.
Base cases:

If size == 0, return 0.
If size == 1, return 1.

For size >= 2:

If S[0] != S[1], return 1 + foo(S+1, size-1).
If S[0] == S[1], return foo(S+1, size-1).

Therefore, for a non-empty array of size $n$ ,

$foo (S, n) = 1 + # {i : 0 \leq i < n - 1, S [i] \neq = S [i + 1]} .$

The leading 1 represents the last run.

Apply this to

$A = {0, 1, 2, 2, 2, 0, 0, 1, 1} .$

Adjacent comparisons:

$0 \neq = 1$ : add 1
$1 \neq = 2$ : add 1
$2 = 2$ : add 0
$2 = 2$ : add 0
$2 \neq = 0$ : add 1
$0 = 0$ : add 0
$0 \neq = 1$ : add 1
$1 = 1$ : add 0

Total adjacent changes = 4.

Add the base-case contribution:

$4 + 1 = 5.$

Tempting wrong path: count only adjacent changes, producing 4. This breaks at the base case size == 1, which returns 1 for the final run.

Verification: The runs are [0], [1], [2,2,2], [0,0], [1,1]. There are exactly 5 runs.

Question 4 · Programming and Data Structures · 2024_Set1 MCQ

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?

A.
The program will not terminate
B.
The program will terminate with no output
C.
The program will terminate with 4321 as output
D.
The program will terminate with 1234 as output

Correct Answer:

Step-by-Step Solution

Insight: The recursive call happens before the print statement, so characters are stored on the call stack during the reading phase and printed in reverse order during the unwinding phase.

Exam route: Input is 1234\n. The function reads each character and recurses until it hits \n. The \n frame returns without printing. As the stack unwinds, the frames for 4, 3, 2, 1 print their characters in reverse order. Output is 4321.

Learning route:

This is a recursive string traversal question, recognisable because a character is read, then recursion occurs, then the character is printed.
Each recursive call has its own local variable a. The first condition reads a character and recurses only if that character is not newline.
For input 1234 followed by newline:

call 1 reads '1' and recurses;
call 2 reads '2' and recurses;
call 3 reads '3' and recurses;
call 4 reads '4' and recurses;
call 5 reads newline and does not recurse.

In the newline call, the second condition also fails, so it prints nothing and returns.
During unwinding:

call 4 prints its saved '4';
call 3 prints its saved '3';
call 2 prints its saved '2';
call 1 prints its saved '1'.

Thus the program terminates and outputs 4321.

Tempting wrong path: claim the output is 1234. This breaks because the print statement is executed after the recursive call, meaning the deepest frame prints first.

Verification: The stack saves '1', '2', '3', '4'. Unwinding pops '4', '3', '2', '1' and prints them. Output is exactly 4321.

Question 5 · Programming and Data Structures · 2021_Set2 NAT

Consider the following ANSI C program.

#include <stdio.h>

int foo(int x, int y, int q)
{
    if ((x <= 0) && (y <= 0))
        return q;
    if (x <= 0)
        return foo(x, y-q, q);
    if (y <= 0)
        return foo(x-q, y, q);
    return foo(x, y-q, q) + foo(x-q, y, q);
}

int main()
{
    int r = foo(15,15,10);
    printf("%d", r);
    return 0;
}

The output of the program upon execution is __________.

Correct Answer:

60.00

Step-by-Step Solution

Insight: The function acts as a path counter on a 2D grid, stepping by $q$ in either the $x$ or $y$ direction, with base cases returning $q$ when both coordinates drop to $\leq 0$ .

Exam route: Trace the recursive tree for foo(15, 15, 10). Notice the symmetric reduction and how boundary conditions collapse the tree into simple additions of the constant $q = 10$ .

Learning route:

This is a multi-variable path counting question, recognisable by two coordinate arguments reducing independently in separate recursive branches.
The function foo(x, y, q) has constant q = 10. Let's trace f(x, y) = foo(x, y, 10).
Base cases:

If $x \leq 0$ and $y \leq 0$ , return $10$ .
If $x \leq 0$ , return $f (x, y - 10)$ .
If $y \leq 0$ , return $f (x - 10, y)$ .

Recursive step: If $x > 0$ and $y > 0$ , return $f (x, y - 10) + f (x - 10, y)$ .
Calculate $f (15, 15)$ :

$f (15, 15) = f (15, 5) + f (5, 15)$

Calculate $f (15, 5)$ :

$f (15, 5) = f (15, - 5) + f (5, 5)$
$f (15, - 5)$ : Since $y \leq 0$ , it returns $f (5, - 5) \to f (- 5, - 5) = 10$ .
$f (5, 5) = f (5, - 5) + f (- 5, 5) = 10 + 10 = 20$ .
So, $f (15, 5) = 10 + 20 = 30$ .

Calculate $f (5, 15)$ :

By symmetry, $f (5, 15) = f (5, 5) + f (- 5, 15) = 20 + 10 = 30$ .

Final result: $f (15, 15) = 30 + 30 = 60$ .

Question 6 · Programming and Data Structures · 2021_Set2 NAT

Consider the following ANSI C function:

int SomeFunction(int x, int y)
{
    if ((x == 1) || (y == 1)) return 1;
    if (x == y) return x;
    if (x > y) return SomeFunction(x - y, y);
    if (y > x) return SomeFunction(x, y - x);
}

The value returned by SomeFunction(15, 255) is __________.

Correct Answer:

15.00

Step-by-Step Solution

Insight: This is the subtraction-based Euclidean algorithm for finding the Greatest Common Divisor (GCD).

Exam route: Recognize the pattern: if $x > y$ , replace $x$ with $x - y$ ; if $y > x$ , replace $y$ with $y - x$ . This computes $g cd (x, y)$ . $g cd (15, 255) = 15$ .

Learning route:

Analyze the conditions:

If $x == y$ , return $x$ .
If $x > y$ , recurse with $(x - y, y)$ .
If $y > x$ , recurse with $(x, y - x)$ .

This is the classic definition of the Euclidean algorithm using subtraction. It preserves the GCD because any common divisor of $x$ and $y$ also divides $x - y$ and $y - x$ .
For SomeFunction(15, 255):

Since $255 > 15$ , it will repeatedly subtract 15 from 255.
This is mathematically equivalent to finding the remainder of 255 divided by 15.
$255 = 15 \times 17$ , so the remainder is 0.
The recursion will reach SomeFunction(15, 15) after 16 subtractions.
When $x == y$ (15 == 15), it returns 15.

Verification: $g cd (15, 255) = 15$ because 15 divides 255 exactly.

Try a question

Login to view the complete previous-year questions and solutions

Personalised first. High quality throughout.

Built around you, not around a syllabus PDF

Revision that hits your weak spots

Questions calibrated to the real exam

Notes written for recall, not for volume

One place for everything

Honest progress

Unlock the whole course

Recursion and Recursive Program Analysis PYQs for GATE CS

Boundary and Scope of Recursive Traversal

Pointer Arithmetic in Recursive Steps

Recursion and Recursive Program Analysis: Solved Questions with Step-by-Step Explanations (6 Problems)

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

More previous year questions (pyqs) in this unit