PadhaikoAll subjects

Past exam question: 2065 Shrawan (Regular / Back), Q4

Data Structure and Algorithms · 8 marks

Open in the Padhaiko app

Topic: Recursion

Question

'A junction or a object calls itself', Explain this statement using the idea behind it. Give recursive algorithm for Fibonacci series and TOH (tower of honoi).

Solution

Meaning of "A Function Calls Itself": This statement describes recursion: a function solves a large problem by invoking itself on one or more strictly smaller instances of the same problem, relying on the call stack to preserve each pending frame until a base case terminates the chain and unwinds results back up.

Recursive Algorithm for Fibonacci Series (F(0)=0, F(1)=1):

Algorithm FIB(n):
1. If n == 0: Return 0
2. If n == 1: Return 1
3. Return FIB(n - 1) + FIB(n - 2)

// To print first k terms:
For i = 0 to k - 1: Print FIB(i)

Recursive Algorithm for Tower of Hanoi (TOH):

Algorithm TOH(n, src, aux, dst):
1. If n == 1:
       Print "Move disk 1 from", src, "to", dst
       Return
2. TOH(n - 1, src, dst, aux)
3. Print "Move disk", n, "from", src, "to", dst
4. TOH(n - 1, aux, src, dst)
Answer:

A function calling itself (recursion) reduces problems toward a base case via stacked activation frames. FIB(n) returns n for else FIB(n-1) + FIB(n-2), and TOH(n, src, aux, dst) moves disks to aux, disk to dst, and disks from aux to dst.

All past exam questions for Data Structure and Algorithms