Comparing Recursion, Iterators, and Generators with Practical Examples

Course: Python Training

Topic: Comparing Recursion, Iterators, and Generators with Practical Examples

Course Link: Python Training Course

Demo Link: Register for a Course Demo

Website: JustAcademy

1. Introduction

Python provides several techniques for controlling how computations are performed and how values are produced. Recursion, iterators, and generators are three important concepts that help programmers solve problems, process sequences, and manage data efficiently.

Although these concepts can be used together, they serve different purposes:

• Recursion: A programming technique in which a function calls itself to solve a smaller version of a problem.
• Iterators: Objects that produce values one at a time and maintain their current iteration state.
• Generators: A convenient way to create iterators using functions with the yield keyword or generator expressions.

Understanding the differences helps developers choose the right technique for tasks such as calculating factorials, traversing nested structures, processing large files, generating sequences, and building data-processing pipelines.

2. Understanding Recursion in Python

Recursion occurs when a function calls itself, either directly or indirectly, to solve a problem. A recursive solution usually divides a complex problem into smaller subproblems until a simple condition can be handled directly.

2.1 Main Components of Recursion

• Base case: The condition that stops further recursive calls.
• Recursive case: The part of the function that calls itself with a smaller or simpler input.
• Call stack: The mechanism that tracks active function calls and their local variables.

A correct recursive function needs a base case and progress toward that case. Without them, the function may continue calling itself until Python raises a RecursionError.

2.2 Example: Calculating Factorial Using Recursion

The factorial of a non-negative integer is the product of all positive integers up to that number. For example, 5! = 5 × 4 × 3 × 2 × 1 = 120, while 0! = 1.

def factorial(n):
    if n < 0:
        raise ValueError("n must be non-negative")

    if n == 0 or n == 1:
        return 1

    return n * factorial(n - 1)


print(factorial(5))
print(factorial(0))

Output:

120
1

How it works:

1. The function receives the number 5.
2. It calls itself with 4, then 3, then 2, then 1.
3. When the input reaches 1, the base case returns 1.
4. The pending calls multiply their values as they return.
5. The final result is 120.

2.3 Advantages of Recursion

• Produces concise solutions for naturally recursive problems.
• Works well with tree traversal, divide-and-conquer algorithms, and backtracking.
• Can make nested structures easier to process conceptually.
• Often closely matches the mathematical definition of a problem.

2.4 Limitations of Recursion

• Each active call requires stack space.
• Deep recursion can raise RecursionError.
• Repeated calculations can make a recursive solution inefficient if results are not reused.
• It can be harder to debug when many function calls are active.

3. Understanding Iterators in Python

An iterator is an object that returns values one at a time. It remembers its current position so that each request continues from where the previous request stopped.

Python's iterator protocol uses two special methods:

• __iter__() returns an iterator. For an iterator, this normally returns the iterator itself.
• __next__() returns the next value or raises StopIteration when no values remain.

The built-in iter() function obtains an iterator, and next() retrieves the next value from it.

3.1 Example: Using iter() and next()

numbers = [10, 20, 30, 40]

number_iterator = iter(numbers)

print(next(number_iterator))
print(next(number_iterator))
print(next(number_iterator))
print(next(number_iterator))

Output:

10
20
30
40

Explanation: The list is an iterable, while number_iterator is an iterator. Each call to next() advances the iterator to the next element.

3.2 Handling Iterator Exhaustion

numbers = [10, 20]

number_iterator = iter(numbers)

print(next(number_iterator, None))
print(next(number_iterator, None))
print(next(number_iterator, None))

Output:

10
20
None

The optional default argument prevents StopIteration from being raised when the iterator is exhausted. Choose a default value that cannot be confused with a legitimate element when that distinction matters.

3.3 Creating a Custom Iterator

Classes can implement the iterator protocol to control how values are produced. This is useful when iteration involves custom state or business rules.

class CountUp:
    def __init__(self, start, stop):
        self.current = start
        self.stop = stop

    def __iter__(self):
        return self

    def __next__(self):
        if self.current > self.stop:
            raise StopIteration

        value = self.current
        self.current += 1
        return value


counter = CountUp(1, 5)

for number in counter:
    print(number)

Output:

1
2
3
4
5

Explanation: The object stores the current number and the stopping limit. Its __next__() method returns a number and updates the state until the stopping condition is reached.

3.4 Advantages and Limitations of Iterators

Advantages:

• Process elements one at a time.
• Maintain state between successive requests.
• Support custom iteration logic.
• Can work with large or streaming datasets without requiring all results to be stored at once.

Limitations:

• Custom iterator classes require additional code.
• Iterators are generally consumed as values are requested.
• An exhausted iterator normally cannot be restarted; a new iterator must be created from the original iterable when possible.
• Manual calls to next() require attention to exhaustion.

4. Understanding Generators in Python

A generator is a special kind of iterator. Generator functions use yield to produce a value and temporarily suspend execution. When the generator is resumed, it continues from where it stopped, retaining its local variables and execution state.

Unlike a regular function that returns a final result with return, a generator can produce a sequence of results over time.

4.1 Example: Creating a Generator with yield

def generate_numbers():
    yield 10
    yield 20
    yield 30
    yield 40


numbers = generate_numbers()

print(next(numbers))
print(next(numbers))
print(next(numbers))
print(next(numbers))

Output:

10
20
30
40

Explanation:

1. Calling generate_numbers() creates a generator object without immediately executing the function body.
2. The first next() call executes the function until the first yield.
3. The generator returns 10 and suspends its execution.
4. Each subsequent call resumes execution until the next yield.
5. After the final yielded value, another request raises StopIteration.

4.2 Example: Generating a Sequence with a Loop

def even_numbers(limit):
    for number in range(2, limit + 1, 2):
        yield number


for value in even_numbers(10):
    print(value)

Output:

2
4
6
8
10

This generator calculates and yields each even number as it is requested rather than building and returning a complete list.

4.3 Generator Expressions

Generator expressions provide a compact way to generate values lazily. They resemble list comprehensions but use parentheses instead of square brackets.

# List comprehension: creates a list
squares_list = [x * x for x in range(1, 6)]

# Generator expression: produces values on demand
squares_generator = (x * x for x in range(1, 6))

print(squares_list)
print(next(squares_generator))
print(next(squares_generator))

Output:

[1, 4, 9, 16, 25]
1
4

The list comprehension builds the complete list immediately. The generator expression creates an iterator that computes each square when requested.

4.4 Advantages and Limitations of Generators

Advantages:

• Require less code than many custom iterator classes.
• Produce values lazily, which can reduce memory usage.
• Preserve local state between yielded values.
• Are useful for streaming data, pipelines, and potentially large sequences.

Limitations:

• Values are generally produced only once as the generator advances.
• Previously yielded values are not automatically stored for replay.
• Generators cannot normally be indexed or sliced like lists.
• Debugging complex generator pipelines may require tracing the sequence of execution.

5. Comparing Recursion, Iterators, and Generators

These three concepts can solve different programming problems, but they are not interchangeable in every situation. Recursion describes how a problem is solved through repeated function calls, while iterators and generators describe how values are produced sequentially.

6. Practical Comparison: Generating Numbers

Consider a program that needs to produce the numbers from 1 to 5. The same result can be achieved using recursion, a custom iterator, or a generator.

6.1 Using Recursion

def print_numbers(n):
    if n > 5:
        return

    print(n)
    print_numbers(n + 1)


print_numbers(1)

Output:

1
2
3
4
5

This approach prints each number through a recursive call. The base case stops the process after 5.

6.2 Using a Custom Iterator

class NumberIterator:
    def __init__(self, start, end):
        self.current = start
        self.end = end

    def __iter__(self):
        return self

    def __next__(self):
        if self.current > self.end:
            raise StopIteration

        value = self.current
        self.current += 1
        return value


numbers = NumberIterator(1, 5)

for number in numbers:
    print(number)

Output:

1
2
3
4
5

This approach explicitly maintains the current number and implements the iterator protocol.

6.3 Using a Generator

def generate_numbers(start, end):
    current = start

    while current <= end:
        yield current
        current += 1


for number in generate_numbers(1, 5):
    print(number)

Output:

1
2
3
4
5

This generator produces one number at a time and automatically preserves the value of current between calls.

Which Approach Is Better?

• Use recursion when the problem naturally involves smaller versions of itself.
• Use a custom iterator when you need explicit control over iteration state or behavior.
• Use a generator when you want to produce a sequence with minimal implementation code.

7. Practical Example: Calculating Factorial and Producing Results

This example demonstrates that recursion can calculate a result, while a generator can deliver a sequence of calculated results on demand.

7.1 Factorial Using Recursion

def factorial(n):
    if n < 0:
        raise ValueError("n must be non-negative")

    if n <= 1:
        return 1

    return n * factorial(n - 1)


print(factorial(4))
print(factorial(5))

Output:

24
120

7.2 Generating Factorial Values

def factorial_sequence(limit):
    result = 1

    for number in range(1, limit + 1):
        result *= number
        yield number, result


for number, value in factorial_sequence(5):
    print(f"{number}! = {value}")

Output:

1! = 1
2! = 2
3! = 6
4! = 24
5! = 120

The recursive function calculates a factorial for one input. The generator calculates and yields a sequence of factorial values. This example illustrates the difference between solving a recursive problem and producing a stream of results.

8. Practical Example: Traversing Nested Lists

Nested lists contain other lists as elements. Recursion is useful for traversing structures of unknown depth, and a generator can expose the resulting values one at a time.

8.1 Recursive Function to Flatten a List

def flatten_recursive(items):
    result = []

    for item in items:
        if isinstance(item, list):
            result.extend(flatten_recursive(item))
        else:
            result.append(item)

    return result


data = [1, [2, 3], [4, [5, 6]]]

print(flatten_recursive(data))

Output:

[1, 2, 3, 4, 5, 6]

The recursive function processes each nested list and builds a complete flattened list in memory.

8.2 Generator to Flatten a List

def flatten_generator(items):
    for item in items:
        if isinstance(item, list):
            yield from flatten_generator(item)
        else:
            yield item


data = [1, [2, 3], [4, [5, 6]]]

for value in flatten_generator(data):
    print(value)

Output:

1
2
3
4
5
6

The yield from expression delegates iteration to a nested generator. Values are produced as they are requested rather than collected into a single flattened list.

Important distinction: This generator still uses recursion internally, so deeply nested structures can encounter recursion limits. Lazy output does not automatically eliminate every memory or stack limitation.

9. Performance and Memory Considerations

The best approach depends on the input size, the required output, and how the result will be consumed. Avoid assuming that one technique is always the fastest.

Example: List Comprehension vs Generator Expression

# Stores all squares in a list
squares_list = [number ** 2 for number in range(1, 1001)]

# Generates squares lazily
squares_generator = (number ** 2 for number in range(1, 1001))

print(sum(squares_list))
print(sum(squares_generator))

Output:

333833500
333833500

Both approaches calculate the same sum. The list stores all 1,000 squares before summation, while the generator expression produces values as sum() consumes them. Actual performance depends on the computation and environment.

10. Common Mistakes to Avoid

• Missing a recursive base case: Ensure recursion has a stopping condition and moves toward it.
• Ignoring recursion depth: Deep recursive calls may exceed Python's recursion limit.
• Forgetting to advance an iterator: A loop that repeatedly reads state without changing it may never finish.
• Calling next() after exhaustion: Use a default value, a for loop, or appropriate exception handling.
• Expecting a generator to run immediately: Calling a generator function creates a generator object; execution begins when iteration advances it.
• Expecting generators to restart: Create a new generator object when the sequence needs to be traversed again.
• Assuming generators always use constant memory: They may retain local references or depend on data structures that consume significant memory.
• Using recursion unnecessarily: A straightforward loop may be clearer and safer for simple repetitive tasks.

11. Practice Exercises

Exercise 1: Recursive Sum

Write a recursive function that calculates the sum of integers from 1 to n. Include a base case and test the function with several values.

Exercise 2: Custom Iterator

Create a class that returns odd numbers within a specified range. Implement __iter__() and __next__().

Exercise 3: Generator for Prime Numbers

Write a generator that yields prime numbers up to a specified limit. Test it by converting its output into a list.

Exercise 4: Recursive Tree Traversal

Represent a small tree using nested lists or dictionaries and write a recursive function that visits its elements.

Exercise 5: Generator-Based File Processing

Write a generator that reads a text file one line at a time and yields only non-empty lines. Test it using a sample text file.

Exercise 6: Compare Memory Usage

Generate a large sequence using a list comprehension and a generator expression. Compare their memory usage with Python's sys.getsizeof() and discuss why that measurement does not include the complete memory retained by referenced objects.

12. Interview Questions and Answers

Q1. What is recursion?

Answer: Recursion is a technique in which a function calls itself to solve a smaller version of a problem until it reaches a base case.

Q2. What is an iterator?

Answer: An iterator is an object that implements the iterator protocol and provides successive values through __next__().

Q3. What is a generator?

Answer: A generator is a type of iterator commonly created with a function containing yield or with a generator expression.

Q4. What is the difference between return and yield?

Answer: return finishes a function and provides its result. yield produces a value and suspends a generator so that execution can resume later.

Q5. Are all generators iterators?

Answer: Yes. Generator objects implement the iterator protocol, allowing them to be used with next() and for loops.

Q6. Can recursion and generators be combined?

Answer: Yes. A recursive generator can use yield from to produce values from recursive calls, such as when traversing nested structures.

Q7. Why can recursion be inefficient?

Answer: Recursive calls use stack space, and repeated subproblems can cause redundant computation. Memoization, dynamic programming, or iteration may improve a particular solution.

Q8. Why are generators useful for large data?

Answer: They produce values on demand and can avoid storing the entire output sequence in memory.

Q9. What is StopIteration?

Answer: It is the exception that signals that an iterator has no more values to produce.

Q10. When should a custom iterator class be used instead of a generator?

Answer: A custom iterator class can be useful when explicit state management, multiple methods, or a more specialized object interface is required. For straightforward sequential generation, a generator is often simpler.

13. Quick Revision Checklist

• Recursion solves problems through repeated function calls.
• Every recursive solution needs a suitable base case.
• Iterators provide values through the iterator protocol.
• iter() obtains an iterator and next() retrieves its next value.
• StopIteration indicates that iteration has finished.
• Generators use yield to produce values lazily.
• Generator expressions use parentheses and produce values on demand.
• yield from delegates iteration to another iterable or iterator.
• Generators are useful for processing streams and large sequences.
• The right technique depends on the problem structure, memory needs, and readability.

14. Conclusion

Recursion, iterators, and generators are essential Python concepts with distinct but complementary roles. Recursion is particularly useful for hierarchical and self-similar problems. Iterators provide a standard mechanism for retrieving values sequentially, while generators make it easy to create stateful, lazy sequences without implementing every iterator method manually.

By practicing factorial calculations, sequence generation, custom iteration, and nested-list traversal, you can learn when to apply each technique and how to combine them in practical Python applications.

Learn Python with JustAcademy

Continue developing your Python programming skills through structured learning, coding practice, and practical exercises.

Python Training Course: Explore Python Training

Course Demo: Register for a Course Demo

JustAcademy Website: Visit JustAcademy