12

Phase 3 - Level 2: Advanced Recursion

Chapter 12 • Intermediate

90 min

Phase 3 - Level 2: Advanced Recursion

Introduction

This level covers advanced recursive techniques for number manipulation, mathematical operations, and complex problem-solving patterns.

Key Concepts

Digit Operations Recursively

  • Count digits recursively
  • Reverse number recursively
  • Sum of digits recursively
  • Product of digits recursively

Mathematical Recursion

  • GCD (Greatest Common Divisor) recursively
  • Binary conversion recursively
  • Number to words conversion
  • Combinatorial calculations (nCr)

Advanced Patterns

  • Recursive functions with multiple parameters
  • Helper functions in recursion
  • Accumulator pattern
  • Tail recursion concepts

Recursive GCD (Euclidean Algorithm)

python.js
def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a % b)

Binary Conversion Recursively

python.js
def to_binary(n):
    if n == 0:
        return ""
    return to_binary(n // 2) + str(n % 2)

Problem-Solving Approach

  1. Identify Base Case: When does recursion stop?
  2. Recursive Case: How to reduce problem size?
  3. Combine Results: How to combine subproblem results?
  4. Handle Edge Cases: Zero, negative, single digit

Common Patterns

  • Digit Processing: Extract digit, recurse on remaining
  • Mathematical Operations: Apply operation recursively
  • Conversion Problems: Build result from right to left
  • Combinatorial: Use mathematical formulas recursively

Hands-on Examples

Count Digits Recursively

def count_digits(n):
    # Base case
    if n == 0:
        return 0
    
    # Recursive case
    return 1 + count_digits(n // 10)

# Test
num = int(input("Enter a number: "))
result = count_digits(abs(num))
print(f"Number of digits: {result}")

Base case: 0 has 0 digits. Recursive: 1 digit + count of remaining digits (n//10 removes last digit).

Previous
Phase 3 - Level 1: Basic Recursion
Next
Phase 3 - Level 3: Pattern Recursion

Related Tutorials

🔗Related Content