Iteration and Recursion Exercise Solutions | KalviGavani

How to Use This Page

Welcome to the Class 11 TN Board Computer Science solutions for the Iteration and Recursion chapter. Here is how to get the most from this page:

1. Start with the Key Concepts section to quickly revise definitions, syntax, and core differences between iteration and recursion. 2. Work through each exercise section in order — MCQs, Fill in the Blanks, True or False, Match the Following, Brief Answers, and Detailed Answers. 3. Try each question on your own first, then check the answer and explanation provided. 4. Review the Common Mistakes section before your exam to avoid frequent errors. 5. Use the Exam Checklist as a final revision tool the day before your exam.

Key Concepts (Quick Recap)

Iteration

Iteration means repeating a set of statements using a loop construct. Python provides two primary loop constructs: for and while.

# for loop example — print numbers 1 to 5
for i in range(1, 6):
    print(i, end=" ")
# Output: 1 2 3 4 5

# while loop example — print numbers 1 to 5
i = 1
while i <= 5:
    print(i, end=" ")
    i += 1
# Output: 1 2 3 4 5

Recursion

Recursion is a technique where a function calls itself to solve a smaller sub-problem. Every recursive function must have:

• Base case: The condition under which the function stops calling itself.
• Recursive case: The condition under which the function calls itself with a modified argument.

def factorial(n):
    if n == 0 or n == 1:       # Base case
        return 1
    else:                       # Recursive case
        return n * factorial(n - 1)

print(factorial(5))  # Output: 120

Iteration vs Recursion — Comparison

Recursive Functions in Python — Examples

Factorial

def factorial(n):
    if n == 0 or n == 1:
        return 1
    return n * factorial(n - 1)

# Trace: factorial(4) = 4 * 3 * 2 * 1 * 1 = 24

Fibonacci Series

def fibonacci(n):
    if n <= 0:
        return 0
    elif n == 1:
        return 1
    else:
        return fibonacci(n - 1) + fibonacci(n - 2)

# fibonacci(6) = 8  (series: 0, 1, 1, 2, 3, 5, 8)

GCD (Greatest Common Divisor)

def gcd(a, b):
    if b == 0:
        return a
    else:
        return gcd(b, a % b)

# gcd(48, 18) = gcd(18, 12) = gcd(12, 6) = gcd(6, 0) = 6

Call Stack

When a recursive function calls itself, each call is placed on the call stack. The call stack stores the local variables and return address of each pending call. When the base case is reached, the stack begins to unwind, returning values back through each call.

I. Choose the Best Answer (MCQs)

Question 1

Which of the following best defines recursion?

(a) A loop that runs until a condition is met (b) A function that calls itself to solve a smaller sub-problem (c) A function that calls another function (d) A method to iterate over a list using for loop

Question 2

What happens if a recursive function does not have a base case?

(a) It returns 0 (b) It runs once and stops (c) It causes infinite recursion leading to a stack overflow (d) It automatically converts to an iterative loop

Question 3

Which of the following is an advantage of recursion over iteration?

(a) Recursion always runs faster than iteration (b) Recursion uses less memory than iteration (c) Recursion provides a cleaner and more intuitive solution for problems with natural recursive structure (d) Recursion does not require a base case

Question 4

Consider the following Python function:

def mystery(n):
    if n == 1:
        return 1
    else:
        return n + mystery(n - 1)

What does mystery(5) return?

(a) 5 (b) 15 (c) 120 (d) 10

• mystery(5) = 5 + mystery(4)
• mystery(4) = 4 + mystery(3)
• mystery(3) = 3 + mystery(2)
• mystery(2) = 2 + mystery(1)
• mystery(1) = 1 (base case)
• Unwinding: 1 + 2 + 3 + 4 + 5 = 15

Question 5

In a recursive function, the call stack is used to:

(a) Store global variables only (b) Keep track of each function call's local variables and return address (c) Execute the base case first (d) Convert recursion into iteration automatically

Question 6

What is the output of the following code?

def func(n):
    if n > 0:
        print(n, end=" ")
        func(n - 1)

func(4)

(a) 1 2 3 4 (b) 4 3 2 1 (c) 4 (d) 1

Question 7

The default recursion limit in Python is:

(a) 500 (b) 1000 (c) 10000 (d) No limit

II. Fill in the Blanks

1. The process of a function calling itself is called recursion.

2. The condition that terminates recursive calls is called the base case.

3. In a recursive function, the part where the function calls itself with a smaller input is called the recursive case.

4. When a recursive function has no base case, it results in infinite recursion (or stack overflow).

5. The default maximum recursion depth in Python is 1000.

6. The Python module used to modify the recursion limit is sys (sys.setrecursionlimit()).

7. Iteration uses loops (for/while) to repeat a block of code.

8. Each recursive call adds a new frame to the call stack.

9. The formula for factorial of n is n x (n-1)!, with base case 0! = 1.

10. The Fibonacci sequence starts with 0 and 1 as its first two terms.

11. The GCD of two numbers using recursion is based on Euclid's algorithm.

12. In recursion, the call stack unwinds (or returns) from the base case back to the first call.

III. True or False

IV. Match the Following

Match the items in Column A with the correct items in Column B.

V. Answer Briefly (2-Mark Questions)

Question 1

Define recursion. Give an example.

Recursion is a programming technique where a function calls itself directly or indirectly to solve a problem by breaking it into smaller sub-problems of the same type.

Example:

def factorial(n):
    if n == 0:
        return 1
    return n * factorial(n - 1)

Here, factorial(n) calls factorial(n - 1) to compute the result.

Question 2

What is a base case? Why is it important in recursion?

A base case is the condition in a recursive function under which the function stops calling itself and returns a value directly. It is important because without a base case, the function would call itself infinitely, leading to a stack overflow error. The base case provides the terminating condition that allows the recursion to stop and the call stack to unwind.

Question 3

Differentiate between iteration and recursion.

Question 4

What is the call stack? How does it work in recursion?

The call stack is a data structure that keeps track of active function calls. In recursion, each time a function calls itself, a new frame (containing local variables and the return address) is pushed onto the call stack. When the base case is reached, the function returns a value, and the stack begins to unwind — each pending call receives the return value from the call above it, computes its result, and passes it down. This continues until the original call receives its result.

Question 5

What is the difference between head recursion and tail recursion?

• Head recursion: The recursive call happens before the processing. The function makes the recursive call first and then performs computations with the result.

  # Head recursion example
  def head_rec(n):
      if n > 0:
          head_rec(n - 1)  # Recursive call first
          print(n, end=" ")  # Processing after
  # head_rec(3) prints: 1 2 3

• Tail recursion: The recursive call is the last operation in the function. There is no computation after the recursive call returns.

  # Tail recursion example
  def tail_rec(n):
      if n > 0:
          print(n, end=" ")  # Processing first
          tail_rec(n - 1)  # Recursive call last
  # tail_rec(3) prints: 3 2 1

VI. Answer in Detail (5-Mark Questions)

Question 1

Explain recursion in detail with the example of computing the factorial of a number. Trace the execution for factorial(5).

Recursion is a problem-solving technique where a function calls itself with a smaller input until a base case is reached. It has two essential components:

1. Base case: The terminating condition that returns a known value without further recursion. 2. Recursive case: The part where the function calls itself with a reduced input.

Factorial — Definition: The factorial of a non-negative integer n (written as n!) is the product of all positive integers less than or equal to n.

• 0! = 1 (base case)
• n! = n x (n - 1)! (recursive case)

Python Program:

def factorial(n):
    # Base case
    if n == 0 or n == 1:
        return 1
    # Recursive case
    else:
        return n * factorial(n - 1)

result = factorial(5)
print(f"5! = {result}")
# Output: 5! = 120

Execution Trace for factorial(5):

Call Stack Visualization:

Question 2

Write a recursive Python function to generate the nth Fibonacci number. Explain how it works and discuss its time complexity. Also write an iterative version for comparison.

The Fibonacci sequence is defined as:

• F(0) = 0
• F(1) = 1
• F(n) = F(n - 1) + F(n - 2) for n > 1

Recursive Solution:

def fibonacci_recursive(n):
    # Base cases
    if n <= 0:
        return 0
    elif n == 1:
        return 1
    # Recursive case
    else:
        return fibonacci_recursive(n - 1) + fibonacci_recursive(n - 2)

# Print first 10 Fibonacci numbers
for i in range(10):
    print(fibonacci_recursive(i), end=" ")
# Output: 0 1 1 2 3 5 8 13 21 34

How it works:

Each call to fibonacci_recursive(n) branches into two sub-calls: fibonacci_recursive(n - 1) and fibonacci_recursive(n - 2). This creates a binary tree of calls. For example, fibonacci_recursive(5) makes the following calls:

Time Complexity: The recursive version has an exponential time complexity of O(2^n) because it recomputes the same values many times. This makes it very inefficient for large values of n.

Iterative Solution (for comparison):

def fibonacci_iterative(n):
    if n <= 0:
        return 0
    elif n == 1:
        return 1

    a, b = 0, 1
    for _ in range(2, n + 1):
        a, b = b, a + b
    return b

# Print first 10 Fibonacci numbers
for i in range(10):
    print(fibonacci_iterative(i), end=" ")
# Output: 0 1 1 2 3 5 8 13 21 34

Comparison:

Optimized Recursive Solution (with memoization):

def fibonacci_memo(n, memo={}):
    if n in memo:
        return memo[n]
    if n <= 0:
        return 0
    elif n == 1:
        return 1
    memo[n] = fibonacci_memo(n - 1, memo) + fibonacci_memo(n - 2, memo)
    return memo[n]

print(fibonacci_memo(50))  # Output: 12586269025

With memoization, the time complexity improves to O(n) because each Fibonacci number is computed only once and stored.

Question 3

Explain the working of Euclid's algorithm for GCD using recursion. Write the Python function and trace it for gcd(48, 18). Also write the iterative version.

Euclid's Algorithm is based on the principle that the GCD of two numbers a and b is the same as the GCD of b and a % b. This process is repeated until the remainder becomes 0. The non-zero number at that point is the GCD.

Mathematical Basis:

• gcd(a, 0) = a (base case)
• gcd(a, b) = gcd(b, a % b) (recursive case)

Recursive Python Function:

def gcd(a, b):
    # Base case: if b is 0, a is the GCD
    if b == 0:
        return a
    # Recursive case: call gcd with (b, a % b)
    else:
        return gcd(b, a % b)

result = gcd(48, 18)
print(f"GCD of 48 and 18 = {result}")
# Output: GCD of 48 and 18 = 6

Execution Trace for gcd(48, 18):

Unwinding:

• gcd(12, 6) returns 6
• gcd(18, 12) returns 6
• gcd(48, 18) returns 6

Verification: The divisors of 48 are {1, 2, 3, 4, 6, 8, 12, 16, 24, 48} and the divisors of 18 are {1, 2, 3, 6, 9, 18}. The greatest common divisor is indeed 6.

Iterative Version:

def gcd_iterative(a, b):
    while b != 0:
        a, b = b, a % b
    return a

print(gcd_iterative(48, 18))  # Output: 6

Comparison:

Both versions have the same time complexity of O(log(min(a, b))) because the remainder decreases by at least half every two steps.

Question 4

Write a recursive function to compute the sum of the first n natural numbers. Trace the execution for sum_n(5). Compare it with the iterative approach.

Recursive Function:

def sum_n(n):
    # Base case
    if n == 1:
        return 1
    # Recursive case
    else:
        return n + sum_n(n - 1)

print(sum_n(5))  # Output: 15

Execution Trace for sum_n(5):

Iterative Version:

def sum_n_iterative(n):
    total = 0
    for i in range(1, n + 1):
        total += i
    return total

print(sum_n_iterative(5))  # Output: 15

Mathematical Formula (most efficient):

def sum_n_formula(n):
    return n * (n + 1) // 2

print(sum_n_formula(5))  # Output: 15

Comparison:

Common Mistakes to Avoid

1. Forgetting the base case: Every recursive function must have a base case. Without it, the function calls itself infinitely and causes a RecursionError. Always write the base case first.

2. Incorrect base case condition: Using n == 1 instead of n <= 1 in factorial can cause errors for negative inputs. Always consider edge cases like n = 0 or n < 0.

3. Not making progress toward the base case: In the recursive case, the argument must move closer to the base case. For example, factorial(n) must call factorial(n - 1), not factorial(n) or factorial(n + 1).

4. Confusing iteration and recursion: Do not use a loop inside a recursive function to do the same job, and do not call a function inside a loop if recursion handles the repetition. Pick one approach and use it consistently.

5. Using recursion for simple counting: If a problem can be solved with a simple loop, prefer iteration. Recursion adds memory overhead (call stack) and is harder to debug. Use recursion only when the problem has a natural recursive structure.

6. Returning inside a loop instead of after it: In iterative solutions, students sometimes return inside the loop, which exits the function prematurely. Make sure return is placed correctly — outside the loop when you need the final accumulated result.

7. Stack overflow for large inputs: Python's default recursion limit is 1000. For inputs larger than this, recursion will fail. Use sys.setrecursionlimit() to increase the limit cautiously, or switch to an iterative approach.

8. Misunderstanding the call stack order: Remember that the call stack unwinds in reverse order — the last call returns first. Do not assume calls execute in the order they were made; the deepest call completes first.

9. Off-by-one errors in Fibonacci: The Fibonacci sequence starts with F(0) = 0, F(1) = 1. Many students write base cases as n == 1 returning 1 and n == 2 returning 1, which shifts the index. Be consistent with 0-based or 1-based indexing.

10. Not handling negative or zero inputs: Recursive functions like factorial(-1) or fibonacci(-5) can cause infinite recursion or incorrect results if not handled. Always add input validation for edge cases.

Exam Checklist

Before your exam, make sure you can do the following:

• [ ] Define iteration and recursion clearly and distinguish between them
• [ ] Identify the base case and recursive case in any recursive function
• [ ] Write recursive Python functions for: factorial, Fibonacci, GCD (Euclid's algorithm), and sum of natural numbers
• [ ] Trace the execution of a recursive function step by step, showing the call stack
• [ ] Explain what happens when a base case is missing (stack overflow / RecursionError)
• [ ] Convert a recursive function to an iterative version and vice versa
• [ ] Compare iteration and recursion across: memory usage, speed, code readability, and appropriate use cases
• [ ] Define and explain the call stack and how it works during recursion
• [ ] Calculate the time complexity of recursive Fibonacci (O(2^n)) and explain why memoization improves it to O(n)
• [ ] Write the iterative version of GCD using Euclid's algorithm
• [ ] Explain head recursion vs. tail recursion with examples
• [ ] Identify common errors: missing base case, infinite recursion, off-by-one errors in Fibonacci
• [ ] Know the Python recursion limit (default: 1000) and how to change it with sys.setrecursionlimit()
• [ ] Solve MCQs on call stack behavior, base case identification, and recursion tracing