Recursion and Stack MCQs: 12 Solved Questions on Calls, Outputs and Unwinding

Recursion questions are rarely lost on the definition. Marks disappear when you mix up work done before a recursive call with work done after it, or forget that pending calls return in last-in, first-out order. Base-case drills teach termination; stack-focused recursion problems demand that you track what each suspended frame stores and exactly when it resumes. These mechanics are central to GATE CS Exam Preparation. Activation records, return-value recurrences, output order, digit reversal, explicit stacks and binary recursion all follow one routine: mark the base case, write the argument at every call, record each action before descent, then unwind frames from the top.

Recursion and stack MCQs: activation records and implementation

The call stack is a last-in, first-out collection of activation records with return addresses, parameters and locals. In main -> sum(3) -> sum(2) -> sum(1) -> sum(0), returns run from sum(0) to sum(3), so a stack fits recursion. Use Data Structures MCQs for wider practice.

Q1. Which structure implements recursive procedures?

Kendriya Vidyalaya Sangathan 2017 | Solve this question

Recursive procedures are implemented using:

A. String
B. Queue
C. Stack
D. Linked List

Answer: C. Stack.

New calls finish before their callers resume. Thus the return order sum(0), sum(1), sum(2), sum(3) is last-in, first-out.

Q2. Recursive versus non-recursive time and space

UGC NET 2015 | Solve this question

In general, in a recursive and non-recursive implementation of a problem (program):

A. Both time and space complexities are better in recursive than in non-recursive program.
B. Both time and space complexities are better in non-recursive than in recursive program.
C. Time complexity is better in recursive version but space complexity is better in non-recursive version of a program.
D. Space complexity is better in recursive version but time complexity is better in non-recursive version of a program.

Answer: B. The non-recursive program is better in general.

Iteration usually avoids call overhead and pending records. It tends to use less space and constant-factor time, but not a better asymptotic class: both factorial versions do n multiplications, while recursion retains up to n frames.

Q3. What the stack stores during recursion

Bihar STET 2025 | Solve this question

In the context of recursion, what is the purpose of the "stack" data structure?

A. To store variables and function calls for backtracking
B. To store only variables
C. To store only function calls
D. To store loop counters

Answer: A. Variables and function calls for backtracking.

An activation record stores control and call-specific data. The sum(3) frame remembers n = 3 and where to continue after sum(2) returns, enabling unwinding.

Recursive return-value MCQs: reduce arguments before adding answers

Track current arguments, work at this level and next arguments. Reach the base case before collapsing additions.

Q4. Sum the binary remainders of 513

GATE 2011 | Solve this question

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 function foo when it is called as foo(513, 2)?

A. 9
B. 8
C. 5
D. 2

Answer: D. 2.

The rows (n, n % 2, n / 2) are (513,1,256), (256,0,128), (128,0,64), (64,0,32), (32,0,16), (16,0,8), (8,0,4), (4,0,2), (2,0,1), (1,1,0). The middle column totals 1 + 0 + 0 + 0 + 0 + 0 + 0 + 0 + 0 + 1 = 2, matching 513 = 512 + 1 = (1000000001)_2.

Q5. Sum the even numbers from 100 to 2

UGC NET 2016 | Solve this question

What is the value returned by the function f given below when n = 100?
let f(int n)
{
  if (n == 0) then return n;
  else
    return n + f(n - 2);
}

A. 2550
B. 2556
C. 5220
D. 5520

Answer: A. 2550.

Expand f(100) = 100 + 98 + 96 + ... + 2 + f(0), where f(0) = 0. The 50 positive terms give 2(1 + 2 + ... + 50) = 2 x (50 x 51 / 2) = 2550; zero adds nothing.

Q6. Recursive multiplication after swapping arguments

Accenture 2025 | Solve this question

What will be the output of the following pseudo code?

For input a = 8 & b = 9.
function (input a, input b)
If (a < b)
return function (b, a)
elseif (b != 0)
return (a + function (a, b - 1))
else
return 0

A. 56
B. 88
C. 72
D. 65

Answer: C. 72.

First, function(8,9) -> function(9,8). Then G(b) = 9 + G(b-1), G(0) = 0, gives eight 9s: G(8) = 9 x 8 = 72; the swap adds nothing.

Recursion output MCQs: descent order versus unwind order

Output before a call occurs on descent; output after it occurs on unwind. Two calls surround the print with complete subtraces. The full recursion and stack practice set reinforces these rules; Q7, Q8, Q10 and Q11 require output tracing, branching, binary conversion and reversal.

Q7. Printing binary remainders before recursion

What does the following function print for n = 25?
void fun(int n)
{
     if (n == 0)
        return;
    printf("%d", n%2);
    fun(n/2);
}

A. 11001
B. 10011
C. 11111
D. 00000

Answer: B. 10011.

The arguments are 25, 12, 6, 3, 1, 0. Printing before descent gives 1, 0, 0, 1, 1, or 10011; the opposite order gives binary 11001.

Q8. Two recursive branches around one print

What will be the output of following program?

#include <stdio.h> 
void recursion(int n) 
{    if(n > 0) 
{ recursion(n-2);
 printf("%d ", n); recursion(n - 2); }
 } 
int main()
{
recursion(6);
 return 0; 
}

A. 4 2 6 2 4 2 2
B. 2 4 2 6 2 4 2
C. 2 6 4 2 4 6 2
D. None of these

Answer: B. 2 4 2 6 2 4 2.

Let S(n) = S(n-2), n, S(n-2) and S(0) be empty. Thus S(2) = 2, S(4) = 2 4 2, and S(6) = 2 4 2 6 2 4 2; two calls duplicate the trace.

Q9. Printing digits before and after unwinding

BEL 2007 | Solve this question

Study the following programme
// precondition : x >= 0
public void demo(int x)
{
System.out.print(x % 10);
if( (x / 10) != 0 )
{
demo(x / 10);
}
System.out.print(x % 10);
}
Which of the following is printed as a result of the call demo (1234)?

A. 1441
B. 3443
C. 12344321
D. 43211234

Answer: D. 43211234.

Trace each frame without combining the two print phases:

Descent prints 4 3 2 1; unwinding prints 1 2 3 4, giving 43211234. The deepest frame prints before and after its skipped branch, producing the middle 11.

Stack operation MCQs: reversal, binary conversion and recursion type

A stack reverses encounter order: the last item pushed is popped first. Apply this below.

Q10. Printing a number's binary representation with a stack

Following is C like pseudo code of a function that takes a number as an argument, and uses a stack S to do processing.

void fun (int n)
{
    Stack S; // Say it creates an empty stack S
    while (n > 0)
    {
          // This line pushes the value of n%2 to stack S
          push (&S, n%2);
          n = n/2;
    } 
    // Run while Stack S is not empty
    while (!isEmpty(&S))
        printf("%d ", pop(&S)); // pop an element from S and print it
}
What does the above function do in general?

A. Prints binary representation of n in reverse order
B. Prints binary representation of n
C. Prints the value of Logn
D. Prints the value of Logn in reverse order

Answer: B. Prints binary representation of n.

For n = 13, division pushes 1, 0, 1, 1; popping gives 1, 1, 0, 1, or binary 1101. Printing without the stack gives the reverse, 1011.

Q11. Reversing the word knowledge

Consider the following pseudo code that uses a stack:

declare a stack of characters
while ( there are more characters in the word to read )
{
read a character
push the character on the stack
}
while ( the stack is not empty )
{
pop a character off the stack
write the character to the screen
}
What is output for input “knowledge”?

A. knowegdge
B. egdelwonk
C. lwonkwgde
D. none of the above

Answer: B. egdelwonk.

Push k, n, o, w, l, e, d, g, e, with final e on top. Pop e, g, d, e, l, w, o, n, k to get egdelwonk; last-in, first-out reverses input.

Q12. Classifying two-call Fibonacci recursion

BEL 2023 | Solve this question

The following C function is an example of what type of recursion?

int f(int n)
{
if(n==1)
return 1;
else if(n==0)
return 0;
else
return(f(n-1)+f(n-2));
}

A. Binary
B. Tail
C. Linear
D. Head

Answer: A. Binary.

Each non-base call creates f(n-1) and f(n-2), so the recursion is binary. Also, f(4) = f(3) + f(2) = (f(2) + f(1)) + (f(1) + f(0)) = (1 + 1) + (1 + 0) = 3; it is not tail recursion because addition remains.

Recursion and stack MCQ traps: a four-check solving method

Do not match words such as stack or binary. Trace first.

Check values: foo(513,2) has ten frames but two 1-bits, f(100) has 50 positive terms, recursion(6) duplicates S(4), and demo(1234) prints four digits down and four up.

The short version: practise the trace, then widen the data-structures set

Locate the base case, record descent arguments, mark work around calls, then unwind last-in, first-out. This handles return values, output order and stacks. For an organised sequence, use GATE Guidance by Sanchit Sir. Next try Binary Tree MCQs. Trace one frame at a time.