Data Structures and Algorithms · Unit 4 · 3 hrs
Recursion
Exam-focused notes for Recursion (Data Structures and Algorithms, CSC211): what the TU syllabus asks and how it has actually been tested, with 7 solved past questions from this unit.
What this unit covers
- Principle of Recursion, Comparison between Recursion and Iteration, Tail Recursion
- Factorial, Fibonacci Sequence, GCD, Tower of Hanoi(TOH)
- Applications and Efficiency of Recursion
Factorial, Fibonacci Sequence, GCD, Tower of Hanoi
Write a program to find GCD of two numbers using recursion. [5]
The GCD (Greatest Common Divisor) of two numbers is based on the Euclidean Algorithm: - If b == 0, then GCD(a, b) = a - Otherwise, GCD(a, b) = GCD(b, a % b) This is a naturally recursive problem, and Recursion helps solve problems that are naturally recursi...
Full solved answer →Write a recursive program to find nth fibonacci number. [5]
The Fibonacci sequence is defined as: - F(0) = 0 - F(1) = 1 - F(n) = F(n-1) + F(n-2) for n = 2 This is a naturally recursive problem because the definition of F(n) directly refers to smaller instances of itself. Recursive solutions are well-suited for probl...
Full solved answer →Write a recursive program to find GCD of two numbers. [5]
The GCD (Greatest Common Divisor) of two numbers is based on Euclid's Algorithm: - If b == 0, then GCD(a, b) = a - Otherwise, GCD(a, b) = GCD(b, a % b) This is a naturally recursive problem where each call reduces the problem size until the base case is rea...
Full solved answer →Explain the Tower of Hanoi (TOH) with practical example. [5]
Tower of Hanoi is a classic mathematical puzzle that is naturally recursive in nature. It involves moving a set of disks from one peg to another following specific rules. TOH is one of the best examples of a problem that is naturally recursive and is a key ...
Full solved answer →Principle of Recursion, Comparison between Recursion and Iteration, Tail Recursion
Explain tail recursion with example. Compare recursion with iteration. [5]
--- Tail recursion is a special form of recursion where the recursive call is the last operation performed in the function. That is, after the recursive call returns, there is nothing left to do in the calling function. Because of this property, the compile...
Full solved answer →Write short notes on: a. Tail recursion b. Collision resolution techniques [5]
--- Definition: Tail recursion is a special form of recursion in which the recursive call is the last operation performed in the function. There is no pending computation left to be done after the recursive call returns. Key Characteristics: - The recursive...
Full solved answer →Define recursive algorithm? How do you implement recursive algorithm while writing computer programs? [5]
An algorithm is a process or set of rules to be followed in calculations or other problem-solving operations by a computer. A recursive algorithm is an algorithm that solves a problem by defining the problem in terms of itself. The underlying mechanism is r...
Full solved answer →Make Unit 4 stick
Practice CSC211 with flashcards & quizzes