Loading previous year questions
19 Qs · since 2011 · 34 marks · 1.3 marks/paperMedium yield
GATE tests Recursion primarily through direct execution tracing of recursive C code snippets, stack-unwinding behavior (pre-order vs. post-order execution), and termination/infinit… Guide
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 which foo(n) returns…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));
}
}…#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…#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…foo and 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;
}
}…#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;
}…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?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 when fun1(5) is called isfoo and bar given 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…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);
}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 of fun(5) is _______.void foo(char *a){
if ( *a && *a != ' '){
foo(a+1);
putchar(*a);
}
}
The output of the above function on input "ABCD EFGH" isvoid get(int n)
{
if (n<1) return;
get(n-1);
get(n-3);
printf("%d", n);
}
If get(6) function is being called in main() then how many times will the get() function be invoked before returning to the main()…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 : _____.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?f(p, p), if the value of p is 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;
}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 function foo when it is called as foo(345, 10)…foo when it is called as foo(513, 2)?Topic guide
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).
Stack Unwinding and Reverse Printing
common · MCQ · 1 marks · 2024, 2015, 2011
A recursive function reads or processes input (strings, digits, or characters) and performs output operations (like `putchar` or `printf`) after the recursive call returns, effectively reversing the input or accumulating from bottom to top.
Static Variable and Reference Side Effects in Recursion
common · MCQ · 2 marks · 2016, 2014, 2013
A recursive snippet uses a `static` local 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
common · NAT · 2 marks · 2015, 2014
Evaluating 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
common · MCQ · 2 marks · 2019, 2017, 2014
Analyzing code with subtle bugs such as wrong base cases (e.g., `n < 0` instead of `n <= 0`), postfix decrements in arguments (`foo(val--)`), or unmodified loop variables to identify stack overflow vs non-terminating loops.
Mutual and Multi-branch Recursion
occasional · mixed · 2 marks · 2021, 2017
Two 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)
occasional · mixed · 2 marks · 2025, 2023
Recursive 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
occasional · NAT · 2 marks · 2026, 2014
Recursive 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.
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.
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
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.