GATE CS

Recursion

Tracing recursive programs

Recursion lets a function solve a problem by calling itself on a smaller instance until a base case is reached. Tracing a recursive C program means hand-simulating the call stack. You need three things: the order of side effects such as printf (before a call means on the way in, after a call means on the way out), the value the outermost call returns, and the number of calls made. This page covers static and global state shared across calls, tail and non-tail recursion, mutual recursion, recursion trees with preorder, inorder and postorder placement, and how to turn a call pattern into a recurrence and solve it. The standard results are linear recursion (n+1 calls), halving recursion (floor(log2 n)+2 calls), naive Fibonacci (2F_{n+1}-1 calls) and Tower of Hanoi (2^n - 1 moves).

9 previous-year questions · 9 solved · 6 practice questions

What Happens When a Function Calls Itself

A recursive function calls itself, directly or indirectly through other functions, to solve a smaller instance of the same problem. Conceptually, every call, recursive or not, creates a fresh activation record (a stack frame). It holds that call's own copies of its parameters, its ordinary (non-static) local variables, and the point to return to in the caller. Tracing a recursive program means keeping this call stack by hand: which frame is running now, what each waiting frame still has to do, and in what order frames finish and hand control back. All programs on this page assume #include <stdio.h> and standard C.

Every recursive function needs, and every trace must identify

A base case: at least one condition under which the function returns WITHOUT making another recursive call. If there is none, or it is never reached (for example, a negative argument when the base case is n == 0 and each call does n - 1), the recursion never ends. In practice the stack keeps growing until the program crashes (stack overflow).
A recursive case: the function calls itself on an argument that moves strictly toward the base case, such as a smaller n, a shorter array segment or a narrower range.
What is done BEFORE the recursive call. It runs on the way in, in the order the calls are made.
What is done AFTER the recursive call returns. It runs on the way back out, in the REVERSE order of the calls. The last call made is the first to finish, because calls are Last-In-First-Out on the stack.

EXAM TIP

When tracing by hand, write the call stack as a vertical list. Grow it downward as calls are made, then pop it upward as calls return, writing down each frame's return value as you pop it. Most tracing errors come from mixing up the order of work done on the way in with work done on the way out, so write both phases down and do not trace in your head.

Tracing Order: What Prints vs What Returns

A trace can ask for two different things. One is the sequence of side effects, such as printf output, whose order is often NOT the order in which the calls were made. The other is the final value returned by the outermost call, built by combining the values returned by inner calls. For a function that makes one recursive call per invocation, the rule is simple. A statement placed before the recursive call runs in call order, outermost call first. A statement placed after it runs in reverse call order, innermost call first. For functions with two recursive calls, see the preorder, inorder and postorder list in the next section.

WORKED EXAMPLE

Trace the output of:

void f(int n) {
    if (n == 0)
        return;
    printf("%d ", n);
    f(n - 1);
    printf("%d ", n);
}

for the call f(3);

Solution

Calls being made (the first printf fires here, in this order): f(3) prints 3, f(2) prints 2, f(1) prints 1. f(0) hits the base case and returns at once without printing.
Calls returning (the second printf fires here, in REVERSE order): f(1) resumes and prints 1, f(2) resumes and prints 2, f(3) resumes and prints 3.
Joining the two phases gives 3 2 1 then 1 2 3.

Answer: Output: 3 2 1 1 2 3. That is six numbers, symmetric around the base case, and the base case itself prints nothing.

WORKED EXAMPLE

What does bin(6); print, and how many calls to bin are made?

void bin(int n) {
    if (n == 0)
        return;
    bin(n / 2);
    printf("%d", n % 2);
}

Solution

The only printf comes AFTER the recursive call, so each frame prints on the way back out, innermost first.
Calls: bin(6) calls bin(3) (6/2 = 3), bin(3) calls bin(1) (integer division 3/2 = 1), bin(1) calls bin(0), and bin(0) returns without printing.
Unwinding: bin(1) prints 1 % 2 = 1, bin(3) prints 3 % 2 = 1, bin(6) prints 6 % 2 = 0.
Calls made: bin(6), bin(3), bin(1), bin(0), which is 4 calls.

Answer: It prints 110, the binary form of 6, most significant bit first, using 4 calls. If the printf were moved BEFORE the call, it would print the bits least significant first: 011.

EXAM TIP

When one expression contains two recursive calls, as in return f(n - 1) + f(n - 2);, C does not specify which operand is evaluated first. The returned value and the total number of calls are well defined. The relative order of any output produced inside the two calls is not. When the order of side effects matters, the calls must be in separate statements, as in a = f(n - 1); then b = f(n - 2);.

Recursion Trees and Counting Calls

A recursion tree has one node per function call. The root is the outermost call, and each node's children are the recursive calls that call makes. A function that makes one recursive call per invocation, like factorial, produces a chain. A function that makes two recursive calls, like naive Fibonacci, produces a branching tree whose number of nodes grows exponentially, because every non-base call branches again until each branch reaches a base case. The number of nodes is the total number of calls (time). The longest root-to-leaf path is the largest number of frames on the stack at once (stack space).

CALL COUNT: SINGLE (LINEAR) RECURSION

C (n) = C (n - 1) + 1, C (0) = 1 \Rightarrow C (n) = n + 1

For a function that makes exactly one recursive call, on $n - 1$ , and stops at n == 0 without a further call (for example, a factorial with base case n == 0). $C (n)$ counts the initial call and the base-case call. If the base case is at n == 1 instead (with $n \geq 1$ ), the count is $n$ . Always check where the base case fires.

CALL COUNT: HALVING RECURSION

C (n) = C (⌊ n /2 ⌋) + 1 (n \geq 1), C (0) = 1 \Rightarrow C (n) = ⌊ lo g_{2} n ⌋ + 2 for n \geq 1

For a function that makes one recursive call on n / 2 (integer division) and stops at n == 0, like bin above. The calls that print or do work (those with $n \geq 1$ ) number $⌊ lo g_{2} n ⌋ + 1$ , which is the number of bits of $n$ . The extra call is the base case n == 0.

CALL COUNT: NAIVE FIBONACCI (TWO CALLS, ON N-1 AND N-2)

T (n) = T (n - 1) + T (n - 2) + 1, T (0) = T (1) = 1 \Rightarrow T (n) = 2 F_{n + 1} - 1

For a function with base cases n == 0 and n == 1 that makes no further calls, and otherwise calls itself on $n - 1$ and $n - 2$ . The $+ 1$ counts the current call. $F_{k}$ is the standard Fibonacci sequence $F_{0} = 0, F_{1} = 1, F_{k} = F_{k - 1} + F_{k - 2}$ . Of the $2 F_{n + 1} - 1$ calls, $F_{n + 1}$ are base-case calls (leaves) and $F_{n + 1} - 1$ make further calls. The count grows as $Θ (φ^{n})$ , where $φ = (1 + 5) /2 \approx 1.618$ .

WORKED EXAMPLE

How many calls in total (nodes in the recursion tree) does naive fib(4) make, where fib(0) and fib(1) are base cases that make no further calls?

Solution

Let T(n) be the total number of calls. T(0) = 1 and T(1) = 1, because each is just the base-case call itself.
T(2) = T(1) + T(0) + 1 = 1 + 1 + 1 = 3.
T(3) = T(2) + T(1) + 1 = 3 + 1 + 1 = 5.
T(4) = T(3) + T(2) + 1 = 5 + 3 + 1 = 9.
Check with the closed form: $2 F_{5} - 1 = 2 \times 5 - 1 = 9$ .

Answer: fib(4) makes 9 calls: the root call, plus 5 calls in the fib(3) subtree and 3 calls in the fib(2) subtree.

Where the statement sits decides the order, for a function with two recursive calls written as separate statements (first call, then second call)

Statement BEFORE both calls: it runs when a node is first entered, which is preorder (node, then first subtree, then second subtree).
Statement BETWEEN the two calls: inorder (first subtree, then node, then second subtree).
Statement AFTER both calls: postorder (first subtree, then second subtree, then node).

EXAM TIP

Do not confuse the DEPTH of a recursion tree, which sets the stack space, with its number of NODES, which sets the total time. For branching recursion they differ hugely. For $n \geq 1$ , fib(n) never has more than $n$ frames on the stack at once, yet it makes $Θ (φ^{n})$ calls. That is linear stack space and exponential time.

Recursion with Static and Global Variables

A static local variable in a recursive function has static storage duration. There is exactly one copy of it, it exists for the whole run of the program, and it is initialised once, before execution begins. The line static int count = 0; does not reset it when the function is entered again. Unlike an ordinary local variable, it gets no fresh copy in each activation record. A global variable is likewise one copy shared by all calls. So a change made by one call is seen by every later call, including later top-level calls. Its value depends on how many times the function has ALREADY run in this program, not only on the current call's parameters.

WORKED EXAMPLE

What does the first call f(3) in a program return, given

int f(int n) {
    static int count = 0;
    count++;
    if (n <= 0)
        return count;
    return f(n - 1);
}

Solution

count starts at 0 and is incremented on EVERY call, including the one where the base case fires.
f(3): count becomes 1, then it recurses. f(2): count becomes 2, then it recurses. f(1): count becomes 3, then it recurses. f(0): count becomes 4, and since n <= 0 it returns count = 4.
Each frame just does return f(n - 1);, so 4 is passed back up unchanged.

Answer: The first call f(3) returns 4, the number of times f has been called so far in the run, not 3.

EXAM TIP

Two traps. (1) Call f(3) a SECOND time in the same program and count continues from 4 (to 5, 6, 7, 8), so the call returns 8. (2) Replace static int count = 0; with a plain local int count = 0; and each call gets its OWN count starting at 0, so the base case sees count = 1 and f(3) returns 1. Always check the storage class before assuming shared state.

Tail Recursion vs Non-Tail Recursion

A recursive call is a tail call if it is the last thing the current call does: nothing happens after it returns (no arithmetic, no further statement, no combining of results). A function is tail recursive when every recursive call in it is a tail call. This depends on WHERE the call sits and what follows it. It does not depend on how many parameters the function takes. Passing an accumulator is the standard way to turn a non-tail-recursive function into a tail-recursive one: return n + sum(n - 1); becomes return sumAcc(n - 1, acc + n);, where the addition is done before the call, as an argument.

Property	Tail recursive	Non-tail (general) recursive
Work after the recursive call returns	None: the call's result is returned directly, or a `void` function simply ends	Some (e.g. add `n`, multiply, combine two results)
Typical shape	`return f(n - 1, updatedAcc);`	`return n + f(n - 1);` or `return f(n - 1) + f(n - 2);`
Rewriting as a loop	Always, mechanically: parameters become loop variables	Needs an explicit stack in general. Many simple cases (e.g. `n * fact(n - 1)`) can be rewritten by hand as a loop with an accumulator
Stack frames needed	One, if the compiler performs tail-call optimisation; otherwise one per call	One per unfinished call, i.e. proportional to the recursion depth

EXAM TIP

The C standard does NOT require compilers to perform tail-call optimisation. Treat 'tail recursive' as a property of the code (is the recursive call the last action, with nothing left to do?). Do not assume that a tail-recursive C function runs in constant stack space unless the question says the compiler optimises tail calls.

Mutual Recursion

Two or more functions are mutually recursive when each calls the other, so neither is defined purely in terms of itself. In C, the function called before its definition must be declared first with a prototype, e.g. int isOdd(int n);. You trace mutual recursion exactly like single-function recursion, with one call stack, except that consecutive frames belong to DIFFERENT functions. Each chain still needs a base case, and that base case may belong to either function.

WORKED EXAMPLE

Trace the value returned by isEven(4), given

int isOdd(int n);

int isEven(int n) {
    if (n == 0)
        return 1;
    return isOdd(n - 1);
}

int isOdd(int n) {
    if (n == 0)
        return 0;
    return isEven(n - 1);
}

Solution

isEven(4): n != 0, so it calls isOdd(3).
isOdd(3): n != 0, so it calls isEven(2).
isEven(2): n != 0, so it calls isOdd(1).
isOdd(1): n != 0, so it calls isEven(0).
isEven(0): base case, returns 1.
This 1 is passed back unchanged through isOdd(1), isEven(2) and isOdd(3) up to isEven(4).

Answer: isEven(4) returns 1 (4 is even), after a chain of 5 calls. In general, for $n \geq 0$ , isEven(n) makes $n + 1$ calls. For a negative argument, n never reaches 0 and the recursion does not terminate.

From a Recursive Definition to a Count or Closed Form

Once you know a recursive function's call pattern, its call count (or running time) satisfies a recurrence. You can solve that recurrence into a closed form, a formula in n with no reference to smaller cases. The usual methods are repeated substitution (unrolling) or reading off the shape of the recursion tree.

UNROLLING SINGLE RECURSION ON N-1

T (n) = T (n - 1) + c, T (0) = c_{0} \Rightarrow T (n) = c_{0} + n c = Θ (n)

Holds when each non-base call does a constant amount of work $c$ and makes exactly one recursive call on $n - 1$ , and the base case at $n = 0$ costs $c_{0}$ . Substitute $T (n - 1) = T (n - 2) + c$ repeatedly: $T (n) = T (n - k) + k c$ , then put $k = n$ .

TWO RECURSIVE CALLS ON N-1 (TOWER OF HANOI MOVES)

M (n) = 2 M (n - 1) + 1, M (0) = 0 \Rightarrow M (n) = 2^{n} - 1

Unrolling gives $M (n) = 2^{k} M (n - k) + (2^{k} - 1)$ ; put $k = n$ . The same shape counts calls when the base case is n == 0 and is itself counted: $C (n) = 2 C (n - 1) + 1, C (0) = 1 \Rightarrow C (n) = 2^{n + 1} - 1$ .

How to turn a recursive count into a closed form

Write the recurrence directly from the code: how many recursive calls does one call make, and on what smaller arguments? Count only what the question asks for (calls, printfs, additions, moves).
Find the base case: the argument at which it fires and what it contributes to the count.
Unroll the recurrence a few steps, substituting it into itself, until a pattern in the unrolling depth k appears.
Choose the k that reaches the base case (k = n for n-1 steps, about log2 n for halving) to get a formula in n alone.
Check the closed form against two or three small values traced by hand (n = 0, 1, 2) before trusting it for a numeric answer.

WORKED EXAMPLE

Find a closed form for the number of times printf runs when g(n) is called, for $n \geq 0$ :

void g(int n) {
    if (n == 0)
        return;
    printf("*");
    g(n - 1);
    printf("*");
}

Solution

Let P(n) be the number of printf calls made by g(n). Each call with n > 0 does one printf before the recursive call and one after it, so P(n) = 2 + P(n-1).
Base case: P(0) = 0, because g(0) returns at once without printing.
Unroll: P(n) = 2 + P(n-1) = 4 + P(n-2) = ... = 2k + P(n-k). With k = n, P(n) = 2n + P(0) = 2n.
Check: P(1) = 2 and P(2) = 4, which match a hand trace.

Answer: P(n) = 2n. This matches the earlier trace of f(3), which printed 6 = 2 × 3 numbers.

WORKED EXAMPLE

For the program below, how many lines does hanoi(3, 'A', 'C', 'B'); print, and how many calls to hanoi does it make in total, including the first one?

void hanoi(int n, char from, char to, char via) {
    if (n == 0)
        return;
    hanoi(n - 1, from, via, to);
    printf("%c -> %c\n", from, to);
    hanoi(n - 1, via, to, from);
}

Solution

Moves (lines printed): each call with n > 0 prints once and makes two calls on n-1, so M(n) = 2M(n-1) + 1 with M(0) = 0.
M(1) = 1, M(2) = 3, M(3) = 7. This agrees with $2^{3} - 1 = 7$ .
Calls: C(n) = 2C(n-1) + 1 with C(0) = 1, because hanoi(0) is itself a call.
C(1) = 3, C(2) = 7, C(3) = 15. This agrees with $2^{3 + 1} - 1 = 15$ .

Answer: 7 lines (moves) and 15 calls. The 8 calls with n = 0 print nothing.

PREVIOUS-YEAR QUESTIONS

9 questions from the CS papers

Try each question first, then open the answer. We placed each question under a topic ourselves; the exam paper does not label topics.

See these papers in full: GATE CSE 2026 Set 1 · GATE CSE 2026 Set 2 · GATE CSE 2025 Set 1 · GATE CSE 2024 Set 1 · GATE CSE 2023 · GATE CSE 2020 · GATE CSE 2018

GATE 2026 CS1 Q.61

GATE 2026 · CS1Q.61 · 2 marks · 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.

Answer and solution

GATE 2026 CS1 Q.61: answer and solution

See the question in the paper

Tap to open full size

GATE 2026 CS1 Q.61: answer and solution

GATE 2026 CS2 Q.61

GATE 2026 · CS2Q.61 · 2 marks · 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.

Answer and solution

GATE 2026 CS2 Q.61: answer and solution

See the question in the paper

Tap to open full size

GATE 2026 CS2 Q.61: answer and solution

GATE 2025 CS1 Q.61

GATE 2025 · CS1Q.61 · 2 marks · 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)

Answer and solution

GATE 2025 CS1 Q.61: answer and solution

See the question in the paper

Tap to open full size

GATE 2025 CS1 Q.61: answer and solution

GATE 2024 CS1 Q.19

GATE 2024 · CS1Q.19 · 1 mark · 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?

GATE 2024 CS1 question 19: The question shows two side-by-side C code panels separated by a vertical divider line (a typical two-column print layout… — Figure from the GATE 2024 CS1 paper. It is part of the question.

(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

Answer and solution

GATE 2024 CS1 Q.19: answer and solution

GATE 2023 CS Q.36

GATE 2023 · CSQ.36 · 2 marks · MCQ

Consider the following program:

int main()
{
   f1();
   f2(2);
   f3();
   return(0);
}

int f1()
{
   return(1);
}

int f2(int X)
{
   f3();
   if (X==1)
     return f1();
   else
     return (X*f2(X-1));
}

int f3()
{
   return(5);
}

Which one of the following options represents the activation tree corresponding to the main function?

GATE 2023 CS question 36: Four candidate activation (call) trees, each rooted at a node labeled 'main': (A) main has three children f1, f2, f3 (left… — Figure from the GATE 2023 CS paper. It is part of the question.

(A)
Figure — main → (f1, f2, f3); the f2 node → (f3, f2); that inner f2 node → (f3, f1)
(B)
Figure — main → (f1, f2, f3); below → (f3, f1) only (missing one level of recursive nesting)
(C)
Figure — main → (f1); f1 → (f2); f2 → (f3, f1)
(D)
Figure — main → (f1, f2, f3); f2 → (f3, f2, f1) all as one flat row of children

Answer and solution

GATE 2023 CS Q.36: answer and solution

GATE 2023 CS Q.47

GATE 2023 · CSQ.47 · 2 marks · MCQ

Consider the C function 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;
  }
}

When foo is called with a pointer to the root node of the given binary tree, what will it print?

GATE 2023 CS question 47: A binary tree with root node 10. — Figure from the GATE 2023 CS paper. It is part of the question.

(A)
3 8 5 13 11 10
(B)
3 5 8 10 11 13
(C)
3 8 16 13 24 50
(D)
3 16 8 50 24 13

Answer and solution

GATE 2023 CS Q.47: answer and solution

GATE 2020 CS Q.46

GATE 2020 · CSQ.46 · 2 marks · NAT

Consider the following C functions.

int fun1(int n) {
  static int i = 0;
  if (n > 0) {
    ++i;
    fun1(n-1);
  }
  return(i);
}

int fun2(int n) {
  static int i = 0;
  if (n > 0) {
    i = i + fun1(n);
    fun2(n-1);
  }
  return(i);
}

The return value of fun2(5) is ______.

Answer and solution

GATE 2020 CS Q.46: answer and solution

See the question in the paper

Tap to open full size

GATE 2020 CS Q.46: answer and solution

GATE 2018 CS Q.21

GATE 2018 · CSQ.21 · 1 mark · NAT

Consider the following C program:

#include <stdio.h>

int counter = 0;

int calc (int a, int b) {
    int c;

    counter++;
    if (b==3) return (a*a*a);
    else {
        c = calc(a, b/3);
        return (c*c*c);
    }
}

int main (){
    calc(4, 81);
    printf ("%d", counter);
}

The output of this program is _____.

Answer and solution

GATE 2018 CS Q.21: answer and solution

See the question in the paper

Tap to open full size

GATE 2018 CS Q.21: answer and solution

GATE 2018 CS Q.45

GATE 2018 · CSQ.45 · 2 marks · NAT

Consider the following program written in pseudo-code. Assume that x and y are integers.

Count(x,y) {
    if (y != 1) {
        if (x != 1) {
            print("*");
            Count(x/2, y);
        }
        else {
            y = y-1;
            Count(1024, y);
        }
    }
}

The number of times that the print statement is executed by the call Count(1024,1024) is _____.

Answer and solution

GATE 2018 CS Q.45: answer and solution

See the question in the paper

Tap to open full size

GATE 2018 CS Q.45: answer and solution

PRACTICE

6 questions to test yourself

PRACTICE 11 mark · MCQ

Consider the C function

void f(int n) {
    if (n == 0)
        return;
    printf("%d ", n);
    f(n - 1);
    printf("%d ", n);
}

What is printed by the call f(3);?

(A)
3 2 1 0 1 2 3
(B)
3 2 1 1 2 3
(C)
1 2 3 3 2 1
(D)
3 2 1

Answer and solution

Answer: (B)

The base case is n == 0. It returns without a printf, so 0 is never printed.
The FIRST printf, before the recursive call, fires on the way in. The SECOND printf, after the recursive call, fires on the way back out, in reverse order.
f(3) prints 3 and calls f(2); f(2) prints 2 and calls f(1); f(1) prints 1 and calls f(0); f(0) returns without printing.
Unwinding: f(1) resumes and prints 1, f(2) resumes and prints 2, f(3) resumes and prints 3.
Full sequence: 3 2 1 1 2 3.

PRACTICE 22 marks · NAT

Consider the naive (non-memoized) recursive function

int fib(int n) {
    if (n == 0 || n == 1)
        return 1;
    return fib(n - 1) + fib(n - 2);
}

Let $T (n)$ be the total number of times fib is called when fib(n) is executed, counting the initial call and every recursive call, including base-case calls. So $T (0) = T (1) = 1$ . What is the value of $T (5)$ ?

Answer and solution

Answer: $15$

Every call fib(n) with n >= 2 makes exactly one call to fib(n-1) and one to fib(n-2), and also counts itself, so T(n) = T(n-1) + T(n-2) + 1.
Base cases: T(0) = 1 and T(1) = 1 (the call itself, with no further recursion).
T(2) = T(1) + T(0) + 1 = 1 + 1 + 1 = 3.
T(3) = T(2) + T(1) + 1 = 3 + 1 + 1 = 5.
T(4) = T(3) + T(2) + 1 = 5 + 3 + 1 = 9.
T(5) = T(4) + T(3) + 1 = 9 + 5 + 1 = 15.
Check with the closed form $T (n) = 2 F_{n + 1} - 1$ , where $F_{6} = 8$ : $2 \times 8 - 1 = 15$ .

PRACTICE 31 mark · MCQ

Consider the C function

int f(int n) {
    static int count = 0;
    count++;
    if (n <= 0)
        return count;
    return f(n - 1);
}

The first call made to f in the program is f(3). What value does it return?

(A)
3
(B)
4
(C)
0
(D)
Undefined behaviour, because static variables cannot be used inside recursive functions

Answer and solution

Answer: (B)

count is static: there is one copy, shared by all calls to f and kept between them. Entering a new call does NOT reset it.
Every call, including the one that hits the base case, runs count++ before testing n <= 0.
f(3): count becomes 1, calls f(2). f(2): count becomes 2, calls f(1). f(1): count becomes 3, calls f(0). f(0): count becomes 4, and since n <= 0 it returns count = 4.
Each of f(1), f(2) and f(3) just does return f(n - 1);, so 4 is passed back up unchanged.
Final returned value: 4.

PRACTICE 42 marks · MSQ

Which of the following C functions are TAIL RECURSIVE, i.e. the recursive call is the last action performed, with nothing left to do in the current call after it returns?

/* (A) */
int fA(int n) {
    if (n == 0) return 0;
    return n + fA(n - 1);
}

/* (B) */
int fB(int n, int acc) {
    if (n == 0) return acc;
    return fB(n - 1, acc + n);
}

/* (C) */
void fC(int n) {
    if (n == 0) return;
    printf("%d", n);
    fC(n - 1);
}

/* (D) */
int fD(int n) {
    if (n <= 1) return 1;
    return fD(n - 1) + fD(n - 2);
}

(A)
fA
(B)
fB
(C)
fC
(D)
fD

Answer and solution

Answer: (B), (C)

(A): after fA(n - 1) returns, the current call still has to ADD n to the result, so work remains after the call. NOT tail recursive.
(B): the result of fB(n - 1, acc + n) is returned directly. The addition acc + n is computed BEFORE the call, as an argument, not after it. Tail recursive.
(C): the printf runs before the recursive call, and work done before the call does not matter. fC(n - 1) is the last statement and nothing runs after it returns. Tail recursive.
(D): after fD(n - 1) and fD(n - 2) return, their results still have to be ADDED, so work remains after the calls. NOT tail recursive.
Correct answers: B and C.

PRACTICE 52 marks · NAT

Consider the mutually recursive C functions

int isEven(int n);
int isOdd(int n);

int isEven(int n) {
    if (n == 0)
        return 1;
    return isOdd(n - 1);
}

int isOdd(int n) {
    if (n == 0)
        return 0;
    return isEven(n - 1);
}

For the top-level call isEven(7), how many function calls occur in total? Count the initial call isEven(7) itself and every later call, up to and including the call that returns without making a further call.

Answer and solution

Answer: $8$

Each call lowers n by 1 and switches function: isEven(7), isOdd(6), isEven(5), isOdd(4), isEven(3), isOdd(2), isEven(1), isOdd(0).
isOdd(0) hits its base case (n == 0) and returns 0 without a further call.
The chain has 8 calls. In general, isEven(n) makes n + 1 calls for n >= 0.
Check: the 0 returned by isOdd(0) is passed back unchanged to isEven(7), which correctly reports that 7 is not even.

PRACTICE 61 mark · MCQ

Consider the C function

void bin(int n) {
    if (n == 0)
        return;
    bin(n / 2);
    printf("%d", n % 2);
}

What is printed by the call bin(13);?

(A)
1011
(B)
1101
(C)
110
(D)
11010

Answer and solution

Answer: (B)

The printf comes AFTER the recursive call, so each call prints on the way back out, innermost first.
Calls (integer division): bin(13) calls bin(6), which calls bin(3), which calls bin(1), which calls bin(0). bin(0) returns without printing.
Unwinding: bin(1) prints 1 % 2 = 1, bin(3) prints 3 % 2 = 1, bin(6) prints 6 % 2 = 0, bin(13) prints 13 % 2 = 1.
Output: 1101, the binary form of 13 (8 + 4 + 1), most significant bit first. It takes 5 calls, which agrees with $⌊ lo g_{2} 13 ⌋ + 2 = 5$ .

OFFICIAL GATE 2027 SYLLABUS WORDING

Copied from the GATE 2027 syllabus; see all 2027 syllabi.

GATE CS

Recursion

Preparing in Kolkata? IAE Academy's course for GATE CSE.