GATE CSE Recursion PYQs
GATE tests Recursion primarily through direct execution tracing of recursive C code snippets, stack-unwinding behavior (pre-order vs. post-order execution), and… Read the guide
- Questions
- 19
- Asked
- since 2011
- Total marks
- 34
- Marks / paper
- 1.3
19 GATE CSE Recursion PYQs with solutions, from Programming and Data Structures. Browse all GATE CSE PYQs.
Questions
Every official paper that asked this topic, newest first.
- GATE CSE 2026 Set 1 · Q61Consider 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 for whichfoo(n)returns…NAT2 marksMediumSolve - GATE CSE 2026 Set 2 · Q61Consider 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)); } }…NAT2 marksMediumSolve - GATE CSE 2025 Set 1 · Q61
#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…NAT2 marksEasySolve - GATE CSE 2024 Set 1 · Q19Consider the following C program:
#include <stdio.h> void fX(); int main(){ fX(); return 0; } void fX(){ char a; if((a=getchar()) != ' ') fX(); if(a != ' ') putchar(a); }Assume that the input to the program from the command line is 1234 followed by a newline…MCQ1 markEasySolve - GATE CSE 2023 · Q47Consider the C function
fooand the binary tree shown.typedef struct node { int val; struct node *left, *right; } node; int foo(node *p) { int retval; if (p == NULL) return 0; else { retval = p->val + foo(p->left) + foo(p->right); printf("%d ", retval); return retval; } }…MCQ2 marksMediumDiagramSolve - GATE CSE 2021 Set 2 · Q49Consider 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; }…NAT2 marksMediumSolve - GATE CSE 2019 · Q26Consider the following C function.
void convert(int n){ if(n<0) printf("%d",n); else { convert(n/2); printf("%d",n%2); } }Which one of the following will happen when the function convert is called with any positive integer n as argument?MCQ2 marksMediumSolve - GATE CSE 2017 Set 1 · Q35Consider the following two functions.
void fun1(int n) { if(n == 0) return; printf("%d", n); fun2(n - 2); printf("%d", n); } void fun2(int n) { if(n == 0) return; printf("%d", n); fun1(++n); printf("%d", n); }The output printed whenfun1(5)is called isMCQ2 marksMediumSolve - GATE CSE 2017 Set 1 · Q36Consider the C functions
fooandbargiven below:int foo(int val) { int x = 0; while(val > 0) { x = x + foo(val--); } return val; } int bar(int val) { int x = 0; while(val > 0) { x = x + bar(val-1); } return val; }Invocations…MCQ2 marksMediumSolve - GATE CSE 2016 Set 1 · Q35What will be the output of the following C program?
void count(int n){ static int d=1; printf("%d ", n); printf("%d ", d); d++; if(n>1) count(n-1); printf("%d ", d); } void main(){ count(3); }MCQ2 marksMediumSolve - GATE CSE 2015 Set 2 · Q11Consider the following C function.
int fun(int n) { int x=1, k; if (n==1) return x; for (k=1; k<n; ++k) x = x + fun(k) * fun(n-k); return x; }The return value offun(5)is _______.NAT1 markMediumSolve - GATE CSE 2015 Set 2 · Q15Consider the following function written in the C programming language.
void foo(char *a){ if ( *a && *a != ' '){ foo(a+1); putchar(*a); } }The output of the above function on input "ABCD EFGH" isMCQ1 markEasySolve - GATE CSE 2015 Set 3 · Q39Consider the following recursive C function.
void get(int n) { if (n<1) return; get(n-1); get(n-3); printf("%d", n); }Ifget(6)function is being called inmain()then how many times will theget()function be invoked before returning to themain()…MCQ2 marksMediumSolve - GATE CSE 2014 Set 1 · Q12Consider a rooted node binary tree represented using pointers. The best upper bound on the time required to determine the number of subtrees having exactly 4 nodes is . Then the value of is _________.NAT1 markMediumSolve
- GATE CSE 2014 Set 2 · Q40Consider the following function
double f(double x) { if ( abs(x*x - 3) < 0.01) return x; else return f(x/2 + 1.5/x); }Give a value (to 2 decimals) such that will return : _____.NAT2 marksMediumSolve - GATE CSE 2014 Set 2 · Q42Consider the C function given below.
int f(int j) { static int i = 50; int k; if (i == j) { printf("something"); k = f(i); return 0; } else return 0; }Which one of the following is TRUE?MCQ2 marksMediumSolve - GATE CSE 2013 · Q42What is the return value of
f(p, p), if the value ofpis initialized to 5 before the call? Note that the first parameter is passed by reference, whereas the second parameter is passed by value.int f (int &x, int c) { c = c - 1; if (c==0) return 1; x = x + 1; return f(x,c) * x; }MCQ2 marksMediumSolve - GATE CSE 2011 · Q48Common Data for Questions 48 and 49:
Consider the following recursive C function that takes two arguments.
unsigned int foo(unsigned int n, unsigned int r) { if (n>0) return ((n%r) + foo(n/r, r)); else return 0; }What is the return value of the functionfoowhen it is called asfoo(345, 10)…MCQ2 marksEasySolve - GATE CSE 2011 · Q49What is the return value of the function
foowhen it is called asfoo(513, 2)?MCQ2 marksEasySolve
What GATE tests in Recursion
Concepts, patterns, formulas and traps distilled from past papers.
GATE tests Recursion primarily through direct execution tracing of recursive C code snippets, stack-unwinding behavior (pre-order vs. post-order execution), and termination/infinite recursion analysis. Questions frequently incorporate static variables, pointer/reference aliasing, mutual recursion, and tree/array traversals to test whether candidates can systematically maintain call frames. In recent years, the focus has expanded from standard tracing to higher-order mathematical characterizations (e.g., finding the smallest input or maximum output value of composed recurrences).
Core concepts
- Call stack frame allocation, activation records, and unwinding order
- Pre-order actions (before recursive call) vs Post-order actions (after recursive call)
- Base conditions and off-by-one boundary failures causing infinite recursion (Stack Overflow)
- Lifetime and visibility of `static` local variables across recursive frames
- Pass-by-value vs pass-by-reference semantics in recursive parameter mutation
- Postfix (`val--`) vs prefix (`--val`, `++n`) operators inside recursive argument expressions
- Mutual recursion between two or more interdependent functions
- Array slicing via pointer arithmetic (`S + 1`, `size - 1`)
- Tree post-order bottom-up subtree metric computation
Recurring question patterns
Stack Unwinding and Reverse Printing
CommonMCQ1 marks2024, 2015, 2011A recursive function reads or processes input (strings, digits, or characters) and performs output operations (like
putcharorprintf) after the recursive call returns, effectively reversing the input or accumulating from bottom to top.Static Variable and Reference Side Effects in Recursion
CommonMCQ2 marks2016, 2014, 2013A recursive snippet uses a
staticlocal variable or pass-by-reference parameter that persists across activation records. Output depends heavily on tracking the shared state before and after recursive calls.Recursive Call Counting and Recurrence Relations
CommonNAT2 marks2015, 2014Evaluating the total number of function invocations, runtime complexity, or dynamic programming-like recurrence evaluations inside a loop.
Termination Flaws and Infinite Recursion vs Infinite Loop
CommonMCQ2 marks2019, 2017, 2014Analyzing code with subtle bugs such as wrong base cases (e.g.,
n < 0instead ofn <= 0), postfix decrements in arguments (foo(val--)), or unmodified loop variables to identify stack overflow vs non-terminating loops.Mutual and Multi-branch Recursion
Occasionalmixed2 marks2021, 2017Two functions calling each other (
fun1/fun2) or a function making multiple branch calls with parameter arithmetic, requiring candidate to draw or trace a small recursion tree.Structural / Pointer Recursion (Trees and Arrays)
Occasionalmixed2 marks2025, 2023Recursive traversal over data structures (arrays with pointer arithmetic
S+1, binary tree post-order sum) to compute counts, transitions, or subtree properties.Mathematical Abstraction and Composed Recurrences
OccasionalNAT2 marks2026, 2014Recursive definitions encoding mathematical operations (e.g., , Newton-Raphson fixed points, modulo transitions) asking for the smallest input for an output target or maximum attainable return value.
Formulas GATE uses
Total Invocations Recurrence
Used to count the total number of function activations including base cases (e.g., ).
Digit Sum in Base $r$
Used when recursive functions peel off least significant digits/bits via modulo and integer division.
Catalan Convolution Recurrence
Used when tracing recursive loops computing combinations of subproblem products.
Repeated Logarithm / Tower Function
Used for nested recursive functions where the base-case depth grows like an iterated logarithm or tower of powers.
Examiner traps in Recursion
- Postfix operators in arguments: writing `foo(val--)` passes the un-decremented `val`, causing immediate infinite recursion, whereas `foo(--val)` decrements first.
- Static variable persistence: forgetting that a static variable is not reset upon re-entering or unwinding stack frames, leading to incorrect post-unwinding outputs.
- Wrong base case triggering infinite recursion: e.g., using `if (n < 0)` for division by 2, causing `n = 0` to recurse endlessly on `0 / 2 = 0`.
- Evaluation order ambiguity: assuming standard left-to-right operand evaluation when pass-by-reference side effects occur within the same expression (e.g., `f(x, c) * x`).
- Counting only recursive steps rather than total invocations: forgetting to count base case calls (leaf calls) in invocation count questions.
- Failing to observe finite-state transitions in parameter spaces: missing that modulo arithmetic transitions form unreachable states or sink cycles.
How questions are asked
- Trace and predict terminal printed output or return value
- NAT: Find the total number of invocations of a recursive function
- NAT: Find the smallest positive input integer n achieving a target output
- NAT: Find the maximum/minimum possible return value across all valid inputs
- Identify termination behavior (normal termination vs infinite loop vs stack overflow)
- Trace tree/array traversal outputs with structural pointers
Paper trends
Shift from standard single-variable digit/string recursion MCQs to multi-variable branching, mutual recursion, and edge-case termination analysis.
2019, 2017, 2015, 2011
Increase in NAT questions requiring exact integer computation, invocation counts, or reverse-solving for the minimum input size / maximum possible return value.
2026, 2025, 2021
Integration of recursion with core data structures (arrays passed via pointer offsets, binary tree subtree aggregations).
2025, 2023
Difficulty notes
Easy: Single recursive call with direct digit extraction, string reversal, or simple array traversal without static variables (1 mark MCQ/NAT). Medium: Branching recursion (2+ calls per frame), mutual recursion, static variables mutating across recursive steps, or computing invocation trees (2 marks MCQ/NAT). Hard: Composed recurrences requiring inverse function analysis (e.g., smallest requiring power tower calculation), interval modulo invariant analysis, or subtle compiler evaluation/termination traps.