PadhaikoAll subjects

Past exam question: 2072 Ashwin (Regular), Q7

Data Structure and Algorithms · 8 marks

Open in the Padhaiko app

Topic: Recursion

Question

Do you think recursive function is slow? Compare recursive and non-recursive functions. Draw recursion tree for Tower of Hanoi assuming 4 disks.

Solution

Why Recursive Functions Can Be Slower: Yes—compared to an equivalent iterative loop, a recursive function typically runs slower because every recursive call incurs function-call overhead: pushing an activation record (arguments, local variables, return address) onto the call stack, jumping, and popping it upon return. Naive tree-recursive functions (like naive fib(n)) can also recompute identical subproblems exponentially many times.

Recursive vs. Non-Recursive (Iterative) Functions:

AspectRecursive FunctionNon-Recursive (Iterative) Function
Control FlowSelf-calls down to base casefor / while loop until termination condition
Memory Usage stack frames loop variables
SpeedSlower per step due to call/return overheadFaster; no stack-frame allocation overhead
ReadabilityCompact and natural for trees, TOH, DFS, quicksortLonger or requires an explicit manual stack for tree/graph tasks

Recursion Tree for TOH(4, A, B, C) ( Moves):

                                 TOH(4,A,B,C)
                    /                 |                  \
           TOH(3,A,C,B)            [A->C]            TOH(3,B,A,C)
          /      |      \                           /      |      \
   TOH(2,A,B,C) [A->B] TOH(2,C,A,B)          TOH(2,B,C,A) [B->C] TOH(2,A,B,C)
    /   |   \          /    |    \           /    |    \          /    |    \
  T(1) A->C T(1)     T(1) C->B  T(1)       T(1) B->A  T(1)      T(1) A->C  T(1)
  A->B      B->C     C->A       A->B       B->C       C->A      A->B       B->C

(Each leaf T(1) represents the base-case single-disk move printed directly beneath it; total moves = .)

Answer:

Recursive functions are generally slower than loops due to call-stack frame overhead (and potential duplicate subproblems). The 4-disk TOH(4, A, B, C) recursion tree has depth 4 and executes moves.

All past exam questions for Data Structure and Algorithms