W Code - Pattern-Based DSA Learning Platform

Bhanu Bisht

Template

Recursion Template: Pattern, Code & Cheat Sheet

The Recursion pattern is one of the most frequently tested coding interview patterns. Break problems into smaller identical subproblems. This template gives you a reusable code skeleton, pseudocode, and implementation in multiple languages so you can solve 15+ problems using this single mental model.

Difficulty: Medium | Time Complexity: Varies | Space Complexity: O(recursion depth)

When to Use This Template

Use the Recursion template when you see these signals in a problem:

1.Tree traversal — Problems asking to tree traversal

2.Generate combinations — Problems asking to generate combinations

3.Divide and conquer — Problems asking to divide and conquer

Prerequisites: Function calls, Stack concept

Problem count on W Code: 15 problems across Easy, Medium, and Hard difficulty levels.

If the problem does not match these signals, consider alternative patterns.

Pseudocode Template

function solve(input):
    // Base case
    if isBaseCase(input):
        return base_result
    
    // Recursive case
    smallerResult = solve(smaller_input)
    return combine(smallerResult, current)

Python Implementation

python
def solve(input_data):
    """Recursion solution template."""
    result = []
    # Implement recursion logic here
    for item in input_data:
        # Process each item
        result.append(item)
    return result

Java Implementation

java
public Object solve(Object[] input) {
    // Recursion template
    // Implement core logic here
    return null;
}

C++ Implementation

cpp
auto solve(vector<int>& input) {
    // Recursion template
    // Implement core logic
    return result;
}

Variations & Adaptations

The Recursion pattern has several variations you should master:

Variation 1: Linear Recursion

This variation is useful when the problem specifically requires linear recursion. Adapt the main template by modifying the core loop/recursion logic accordingly.

Variation 2: Binary Recursion (Trees)

This variation is useful when the problem specifically requires binary recursion (trees). Adapt the main template by modifying the core loop/recursion logic accordingly.

Variation 3: Divide and Conquer

This variation is useful when the problem specifically requires divide and conquer. Adapt the main template by modifying the core loop/recursion logic accordingly.

Variation 4: Tail Recursion

This variation is useful when the problem specifically requires tail recursion. Adapt the main template by modifying the core loop/recursion logic accordingly.

Common Mistakes & Edge Cases

When implementing Recursion, watch out for:

1.Off-by-one errors — Carefully handle boundary conditions in loops

2.Missing base case — Ensure recursion terminates properly

3.Integer overflow — Use appropriate data types for large inputs

4.Empty input — Handle null/empty arrays, strings, or graphs

5.Single element — Test with minimal inputs

Edge cases to always test:

•Empty input → expected output

•Single element → correct result

•All same elements → no infinite loop

•Maximum constraints → within time limit

Step-by-Step Problem Solving Guide

1.Identify the pattern: Does the problem involve Tree traversal, Generate combinations, Divide and conquer?

2.Choose the template: Select the variation from above that best fits

3.Define variables: Map problem-specific entities to template variables

4.Implement the core logic: Fill in the template skeleton

5.Handle edge cases: Add boundary checks

6.Verify with examples: Trace through sample inputs

7.Analyze complexity: Confirm Varies time and O(recursion depth) space

Frequently Asked Questions

What problems can I solve with the Recursion template?

The Recursion template applies to 15+ problems including: Tree traversal, Generate combinations, Divide and conquer. Look for problems that involve break problems into smaller identical subproblems..

What is the time complexity of Recursion?

The typical time complexity is Varies with space complexity of O(recursion depth). Some variations may differ.

What should I learn before Recursion?

Prerequisites include: Function calls, Stack concept. Make sure you are comfortable with these concepts first.

How do I recognize a Recursion problem in an interview?

Key signals: the problem involves tree traversal; the problem involves generate combinations; the problem involves divide and conquer. Practice identifying these cues by solving at least 10 problems using this pattern.

Practice 15+ Recursion problems on W Code with instant feedback and AI-powered hints. Start your free practice now!

Start Learning Free