Self-checkedTier 1 17 min readpds.recursion-patterns

Recursion patterns

The handful of shapes that nearly every recursive function in an exam has (linear, tail, binary, halving, nested, mutual, backtracking), how to read the output from the order of print and call, how many calls each shape makes, and which recurrence and running time it gives. All examples run for real.

Why it exists

The previous page explained how a recursive call works: a frame per call, winding and unwinding, depth and space. This page is about recognising the shape of a recursive function, because the shape tells you three things at once: what it prints and in which order, how many calls it makes, and its running time. Exam questions repeat the same dozen shapes with new numbers.

Prerequisites

Recursion and the call stack

Precise definitions

Every recursive function has a base case (no recursive call) and a recursive case that moves toward a base case. The shapes differ in how many recursive calls are made, what the argument becomes, and where the work is done.

Shape	Recursive calls	Argument	Typical examples
Linear	1	$n - 1$	factorial, sum of $1..n$ , list length
Tail	1, and it is the last thing done (its result is returned unchanged)	often $n - 1$ with an accumulator	factorial with an accumulator, gcd
Binary (tree)	2	$n - 1$ and $n - 2$	Fibonacci
Doubling	2	$n - 1$ both times	Tower of Hanoi, subsets
Divide and conquer	1 or 2	about $n / 2$	binary search, fast power, merge sort
Nested	the argument is itself a recursive call		McCarthy 91, Ackermann
Mutual	$f$ calls $g$ , $g$ calls $f$		even/odd
Backtracking	a loop of calls, with pruning and undo		permutations, $n$ -queens

Tail call. A call whose value is returned directly (return f(...)) with nothing left to do afterwards. A compiler may reuse the frame, but C does not require it; count one frame per call unless a question says otherwise.
Accumulator. An extra parameter that carries the partial result down, so that the answer is complete at the base case and nothing is multiplied on the way back.
Pre-order and post-order work. Work written before the recursive call happens on the way in (in call order). Work written after it happens on the way out (in reverse call order).

How it works

Reading output from the position of the print

Two lines are enough to decide the order. For the function f in the first self-check question, a print before the call shows the arguments going in (3, 2, 1) and a print after shows them coming back out (1, 2, 3). The function that prints both gives the palindrome 3 2 1 1 2 3. The animation shows the same winding and unwinding for Fibonacci, a function with two calls: the tree shape is why its call count explodes.

Call stack: Fibonacci: fib(4)

Real execution trace

C source

1int fib(int n) {

2 if (n < 2)

3 return n;

4 return fib(n - 1) + fib(n - 2);

GATE model: a frame is parameters + locals + return address.
Real hardware: the compiler also saves the frame pointer and aligns the frame.

Call stacktop ↑

main()

Recursion tree

Trace produced by: real execution of an instrumented C program. gcc (Debian 14.2.0-19) 14.2.0, linux x64. gcc -O0 -fno-omit-frame-pointer -fno-stack-protector -o fib4 fib4.c && ./fib4

Step 0

Execution starts in main, which is about to call fib(4). The stack holds only main's frame.

0 / 31

Stack depth now

Max depth so far

Calls so far

Frame gap, real x86-64

48 B

Recurrence and running time for each shape

If a function does $c$ work apart from its recursive calls, count the calls (or write the recurrence):

Code shape	Recurrence	Result	Where you meet it
one call on $n-1$ , constant work	$T(n) = T(n-1) + c$	$\Theta(n)$	factorial, list length
one call on $n-1$ , linear work	$T(n) = T(n-1) + cn$	$\Theta(n^2)$	selection-sort style
one call on $n/2$ , constant work	$T(n) = T(n/2) + c$	$\Theta(\log n)$	binary search, fast power
one call on $n/2$ , linear work	$T(n) = T(n/2) + cn$	$\Theta(n)$
two calls on $n/2$ , constant work	$T(n) = 2T(n/2) + c$	$\Theta(n)$	tree walks on a balanced tree
two calls on $n/2$ , linear work	$T(n) = 2T(n/2) + cn$	$\Theta(n \log n)$	merge sort
two calls on $n-1$ , constant work	$T(n) = 2T(n-1) + c$	$\Theta(2^n)$	Hanoi, subsets
calls on $n-1$ and $n-2$	$T(n) = T(n-1) + T(n-2) + c$	$\Theta(\varphi^n)$ , $\varphi \approx 1.618$	naive Fibonacci
a loop of $n$ calls on $n-1$	$T(n) = nT(n-1) + c$	$\Theta(n!)$ calls (more work if each call also loops)	permutations

The space is the depth of the recursion (times the frame size), not the number of calls: $\Theta(n)$ for $n-1$ shapes, $\Theta(\log n)$ for halving.

Worked examples

EX 1Linear recursion and its tail-recursive form

Easy

#include <stdio.h>
 
static long fact(int n) {
    return n <= 1 ? 1 : n * fact(n - 1);
}
 
static long fact_acc(int n, long acc) {
    return n <= 1 ? acc : fact_acc(n - 1, acc * n);
}
 
int main(void) {
    printf("%ld %ld\n", fact(10), fact_acc(10, 1));
    return 0;
}

Output:

3628800 3628800

Reading it. In fact, each call must still multiply by n after the inner call returns, so the work waits in the frame. In fact_acc, the product is built on the way down (acc * n) and the base case returns it unchanged: the recursive call is the last thing the function does, a tail call. Both make 10 calls and need $\Theta(n)$ stack as written; a compiler is allowed to turn the second into a loop, but C does not promise it.

EX 2Decimal to binary, printed forwards and backwards

Medium

#include <stdio.h>
 
static void bin(int n) {
    if (n > 0) {
        bin(n / 2);
        printf("%d", n % 2);
    }
}
 
static void rbin(int n) {
    if (n > 0) {
        printf("%d", n % 2);
        rbin(n / 2);
    }
}
 
int main(void) {
    bin(10);
    printf("\n");
    rbin(10);
    printf("\n");
    return 0;
}

Output:

1010
0101

Reading it. The arguments of the calls are 10, 5, 2, 1, 0, and n % 2 gives the remainders 0, 1, 0, 1 in that order (the least significant bit first). rbin prints them in call order: 0101 (the binary number written backwards). bin prints after the inner call, so the last remainder (the most significant bit) comes out first: 1010, the correct binary of 10. A question that moves the printf from after to before the call is testing exactly this. For $n = 0$ both print nothing (a real converter would special-case 0).

EX 3Tower of Hanoi: the moves and the count

Medium

#include <stdio.h>
 
static int moves, verbose;
 
static void hanoi(int n, char a, char b, char c) {
    if (n == 0) return;
    hanoi(n - 1, a, c, b);
    if (verbose) printf("%c->%c ", a, c);
    moves++;
    hanoi(n - 1, b, a, c);
}
 
int main(void) {
    verbose = 1;
    hanoi(3, 'A', 'B', 'C');
    printf("\n");
    verbose = 0;
    for (int n = 1; n <= 5; n++) {
        moves = 0;
        hanoi(n, 'A', 'B', 'C');
        printf("%d ", moves);
    }
    printf("\n");
    return 0;
}

Output:

A->C A->B C->B A->C B->A B->C A->C
1 3 7 15 31

Reading it. To move $n$ disks from a to c using b: move $n-1$ disks out of the way (to b), move the biggest disk, then move the $n-1$ disks on top of it. That is two calls on $n-1$ plus one move: $T(n) = 2T(n-1) + 1$ with $T(0) = 0$ , which gives $T(n) = 2^n - 1$ : 1, 3, 7, 15, 31. For 6 disks, 63 moves. The number of calls (including those with $n = 0$ ) is $2^{n+1} - 1$ , larger than the number of moves; read the question to see which one it asks for.

EX 4Fast power: halving makes the calls logarithmic

Medium

#include <stdio.h>
 
static int calls;
 
static long power(long x, int n) {
    calls++;
    if (n == 0) return 1;
    long h = power(x, n / 2);
    return n % 2 ? h * h * x : h * h;
}
 
int main(void) {
    long a = power(2, 10);
    int c1 = calls;
    calls = 0;
    long b = power(3, 13);
    printf("%ld %d %ld %d\n", a, c1, b, calls);
    return 0;
}

Output:

1024 5 1594323 5

Reading it. power(2, 10) calls with $n = 10, 5, 2, 1, 0$ : five calls and six multiplications (a plain loop would make nine). In general the argument is halved each time, so the number of calls is $\lfloor \log_2 n \rfloor + 2$ for $n \ge 1$ . The same count appears for $3^{13}$ (arguments 13, 6, 3, 1, 0). Compare this with the linear version power(x, n - 1), which makes $n + 1$ calls.

EX 5Binary search, recursively

Medium

#include <stdio.h>
 
static int calls;
 
static int bs(const int *a, int lo, int hi, int key) {
    calls++;
    if (lo > hi) return -1;
    int mid = lo + (hi - lo) / 2;
    if (a[mid] == key) return mid;
    if (a[mid] < key) return bs(a, mid + 1, hi, key);
    return bs(a, lo, mid - 1, key);
}
 
int main(void) {
    int a[16] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53};
    int i = bs(a, 0, 15, 47);
    int c1 = calls;
    calls = 0;
    int j = bs(a, 0, 15, 4);
    printf("%d %d %d %d\n", i, c1, j, calls);
    return 0;
}

Output:

14 4 -1 5

Reading it. Searching for 47: the middle indices examined are 7, 11, 13 and 14, so 4 calls, and the key is found at index 14. Searching for 4 (absent) examines indices 7, 3, 1, 2 and then makes a fifth call with an empty range (lo > hi) that returns $-1$ . Each call halves the range, so a search among $n$ items makes $O(\log n)$ calls: $T(n) = T(n/2) + c$ . The lo + (hi - lo) / 2 form avoids overflow in lo + hi.

EX 6Nested recursion: McCarthy 91 and Ackermann

GATE level

#include <stdio.h>
 
static int mc(int n) {
    return n > 100 ? n - 10 : mc(mc(n + 11));
}
 
static int ack(int m, int n) {
    if (m == 0) return n + 1;
    if (n == 0) return ack(m - 1, 1);
    return ack(m - 1, ack(m, n - 1));
}
 
int main(void) {
    printf("%d %d %d %d %d %d\n", mc(50), mc(99), mc(101), mc(150), ack(2, 3), ack(3, 3));
    return 0;
}

Output:

91 91 91 140 9 61

Reading it. In mc(mc(n + 11)) the inner call must finish first, because its result is the argument of the outer call. For every $n \le 100$ the result is 91; above 100 it is simply $n - 10$ (101 gives 91, 150 gives 140). Trace a small case yourself: mc(99) $=$ mc(mc(110)) $=$ mc(100) $=$ mc(mc(111)) $=$ mc(101) $=$ 91. For Ackermann the same rule applies: evaluate the inner ack(m, n - 1) first, then use it as the second argument. $A(2, 3) = 2 \cdot 3 + 3 = 9$ and $A(3, 3) = 2^{3+3} - 3 = 61$ . These grow extremely fast, which is why exam questions use tiny arguments.

EX 7Mutual recursion

Medium

#include <stdio.h>
 
static int is_odd(int n);
 
static int is_even(int n) {
    return n == 0 ? 1 : is_odd(n - 1);
}
 
static int is_odd(int n) {
    return n == 0 ? 0 : is_even(n - 1);
}
 
int main(void) {
    printf("%d %d %d\n", is_even(10), is_odd(7), is_even(7));
    return 0;
}

Output:

1 1 0

Reading it. is_even(10) calls is_odd(9), which calls is_even(8), and so on, alternating until n is 0. The frames of the two functions alternate on the stack and the depth is $n + 1$ . The declaration static int is_odd(int n); before is_even is needed so that the compiler knows the second function when it reads the first.

EX 8Counting what a backtracking search enumerates

GATE level

#include <stdio.h>
#include <stdlib.h>
 
static int calls;
 
static int subsets(int i, int n) {
    calls++;
    if (i == n) return 1;
    return subsets(i + 1, n) + subsets(i + 1, n);
}
 
static int perms(int used, int n, int k) {
    if (k == n) return 1;
    int t = 0;
    for (int v = 0; v < n; v++)
        if (!(used & (1 << v))) t += perms(used | (1 << v), n, k + 1);
    return t;
}
 
static int cols[8];
 
static int ok(int r, int c) {
    for (int i = 0; i < r; i++)
        if (cols[i] == c || abs(cols[i] - c) == r - i) return 0;
    return 1;
}
 
static int queens(int r, int n) {
    if (r == n) return 1;
    int t = 0;
    for (int c = 0; c < n; c++)
        if (ok(r, c)) {
            cols[r] = c;
            t += queens(r + 1, n);
        }
    return t;
}
 
int main(void) {
    int s = subsets(0, 4);
    printf("%d %d %d %d %d %d\n", s, calls, perms(0, 4, 0), queens(0, 4), queens(0, 6), queens(0, 8));
    return 0;
}

Output:

16 31 24 2 4 92

Reading it.

Subsets of a 4-element set: the two calls at each level stand for the two choices for one element (leave it out, or put it in). This program only counts the leaves, it does not build the subsets: $T(n) = 2T(n-1) + 1$ . The result counts $2^4 = 16$ subsets, and the number of calls is $2^{4+1} - 1 = 31$ .
Permutations of 4 items: 4 choices for the first position, then 3, 2, 1: $4! = 24$ .
$n$ -queens is true backtracking: place one queen per row, try every column, prune the columns attacked by earlier rows (ok), and when a row has no safe column the call returns and the previous row tries its next column (its earlier choice is simply overwritten, which is the "undo"). There are 2 solutions for $n = 4$ , 4 for $n = 6$ and 92 for $n = 8$ .

Cheat box

Print before the call: call order. Print after: reverse order. Both: palindrome (3 2 1 1 2 3).
Decimal to binary: the recursive call must come before the print of n % 2 to get the correct order.
Linear: $T(n) = T(n-1) + c = \Theta(n)$ . Halving: $T(n) = T(n/2) + c = \Theta(\log n)$ . Two halves with linear work: $\Theta(n \log n)$ .
Two calls on $n-1$ : $\Theta(2^n)$ . Hanoi moves $= 2^n - 1$ ; calls (with the empty case) $= 2^{n+1} - 1$ . Fibonacci calls: $2F_{n+1} - 1$ (with fib(0) = 0, fib(1) = 1 and base case $n \le 1$ ).
Fast power: about $\lfloor \log_2 n \rfloor + 2$ calls. Binary search: about $\log_2 n$ probes.
Nested call $f(f(x))$ : evaluate the inner one first. McCarthy: $f(n) = 91$ for $n \le 100$ , else $n - 10$ .
Space is the depth, not the number of calls.
Backtracking: subsets $2^n$ , permutations $n!$ , queens (4, 6, 8) $= 2, 4, 92$ .
Tail calls may be optimised, but C does not require it.

Traps and GATE patterns

Connections

Builds on

Recursion and the call stack

Unlocks

Linked list operationsuses Binary tree traversalsuses Constructing a tree from its traversalsuses

Across subjects

Recurrence relationsusesplanned

Merge sortanalogous-to

Within this subject

Linked list operationsuses Binary tree traversalsuses

Recursion over lists (list operations) and over trees (tree traversals) follows these shapes; the printing order of a traversal is the pre-order, in-order or post-order position of the printf. The recurrence for the running time is solved in recurrence relations. Merge sort is the divide-and-conquer shape with linear work (merge sort). The cost model is the stack from the previous page.

PYQs

13 previous year questions from your book. I re-solved each one myself (13 by running or simulating, 0 by reasoning only); the book's key is shown next to my answer. All PYQs

GATE 2014 · Set 2 · NAT · 2 marksQ12 · page 12 of the book

Consider the following function
#include <math.h>
double f(double x){

if (abs(x*x - 3) < 0.01) return x;
    `

else return f(x/2 + 1.5/x);
}
Give a value q (to 2 decimals) such that f(q) will return
q: _____.

GATE 2026 · Set 2 · NATQ3 · page 17 of the book

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.

GATE 2025 · Set 2 · NAT · 2 marksQ5 · page 18 of the book

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

GATE 2021 · NAT · 2 marksQ9 · page 19 of the book

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 ______ .

GATE 2020 · NAT · 2 marksQ11 · page 19 of the book

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 Some Function(15, 255) is
______

GATE 2018 · NATQ16 · page 20 of the book

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 ____ .

GATE 2015Q24 · page 22 of the book

Consider the following recursive C function.
void 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()?

(a)15
(b)25
(c)35
(d)45

GATE 2015 · Set 2 · NAT · 1 markQ26 · page 22 of the book

Consider 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 of fun (5) is _______.

GATE 2015 · Set 2 · MCQ · 1 markQ27 · page 23 of the book

Consider the following function written 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" is

(a)ABCD EFGD
(b)ABCD
(c)HGFE DCBA
(d)DCBA

GATE 2011 · MCQ · 2 marksQ33 · page 24 of the book

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

year not read yetQ34 · page 24 of the book

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(345, 10) ?

(a)345
(b)12
(c)5
(d)3

GATE 2008 · MCQ · 2 marksQ41 · page 26 of the book

Choose the correct option to fill ?1 and ?2 so that the
program below prints an input string in reverse order.
Assume that the input string is terminated by a
newline character.

void reverse(void) {

int c;

   if (?1) reverse();

?2

}

main() {

printf("Enter Text");

printf("\n");

reverse();

printf("\n");

}

(a)?1 is (getchar() != '\n') ?2 is getchar(c);
(b)?1 is (c = getchar()) != '\n' ?2 is getchar(c);
(c)?1 is (c != '\n') ?2 is putchar(c);
(d)?1 is ((c = getchar()) != '\n') ?2 is putchar(c);

GATE 2012 · MCQQ9 · page 62 of the book

The recurrence relation capturing the optimal
execution time of the Towers of Hanoi problem with
n discs is

(a)T(n) = 2T(n - 2) + 2
(b)T(n)= 2T(n - 1) + n
(c)T(n)= 2T(n/2) + 1
(d)T(n)= 2T(n - 1) + 1

Self-check

Question 1

What does this print?

#include <stdio.h>
 
static void f(int n) {
    if (n == 0) return;
    printf("%d ", n);
    f(n - 1);
    printf("%d ", n);
}
 
int main(void) {
    f(3);
    printf("\n");
    return 0;
}

Show answer

The first printf runs on the way in (3, 2, 1) and the second on the way out (1, 2, 3).

3 2 1 1 2 3

Question 2

How many moves does the Tower of Hanoi need for 6 disks, and how many for 10?

Show answer

$2^6 - 1 = 63$ and $2^{10} - 1 = 1023$ .

Question 3

State the recurrence and the running time of a function that makes two recursive calls on halves of the input and does linear work to combine them.

Show answer

$T(n) = 2T(n/2) + cn$ , which gives $\Theta(n \log n)$ (merge sort).

Question 4

What is the maximum recursion depth of power(x, 1000) in example 4, and of the linear version power(x, n - 1)?

Show answer

The halving version has arguments 1000, 500, 250, 125, 62, 31, 15, 7, 3, 1, 0: 11 active calls at the deepest point (about $\log_2 1000$ ). The linear version has 1001 calls active at once.

Question 5

Using mc from example 6, compute mc(95) by hand.

Show answer

mc(95) = mc(mc(106)) = mc(96) = mc(mc(107)) = mc(97) = mc(mc(108)) = mc(98) = mc(mc(109)) = mc(99) = mc(mc(110)) = mc(100) = mc(mc(111)) = mc(101) = 91. So mc(95) is 91.

Revision card

One-screen revision

Shapes: linear, tail, binary, doubling, divide and conquer, nested, mutual, backtracking.
Print before the call: forward order. After: reverse. Binary conversion: recurse first, then print.
$T(n)=T(n-1)+c$ : $\Theta(n)$ . $T(n)=T(n/2)+c$ : $\Theta(\log n)$ . $T(n)=2T(n/2)+cn$ : $\Theta(n\log n)$ . $T(n)=2T(n-1)+c$ : $\Theta(2^n)$ .
Hanoi: $2^n - 1$ moves. Subsets: $2^n$ . Permutations: $n!$ .
Nested calls: inner first. McCarthy 91: 91 for $n \le 100$ , else $n - 10$ .
Space = depth. Check the base case against the real argument sequence.

References

·Kernighan and Ritchie, The C Programming Language, 2nd ed., Section 4.10 Recursion
·Cormen, Leiserson, Rivest, Stein, Introduction to Algorithms, 3rd ed., Chapter 2 (divide and conquer, merge sort analysis) and Chapter 4 (solving recurrences)

Verification

All C programs on this page are compiled with -Wall -Wextra -Werror and run by npm run verify:c, also under AddressSanitizer and UBSan, and every call count, move count and return value in the text is the printed output of such a program. The call-stack animation is the one from the recursion page (a real run). The recurrences in the summary table are standard results; the call counts and growth rates were additionally checked numerically by an independent audit script (not part of the repository) and against the counts these programs print, but NOT against the textbooks. The textbook chapter numbers were written from memory and have NOT been checked. The prose and the GATE-pattern claims have NOT yet had a human textbook check (the independent second pass is described at the end of these notes). SECOND PASS (2026-11-02, done by the assistant, not a human check): every Self-check question was solved before the printed answer was read and all agreed; the definitions, worked examples, cheat box and traps were read claim by claim and the numbers re-derived by hand (long C programs were not re-read line by line: they are compiled and compared by npm run verify:c, and their printed outputs were checked against the prose). No defect found. Status raised to self-checked; verified needs a textbook or human check.

last verified: never

My notes (saved in this browser)

Recursion and the call stack

Trees and binary trees