Quick guide to types of Recursion

It is a technique where a function calls itself directly or indirectly to solve a problem by breaking it into smaller problems. There are various types of recursion, which are described below with some examples:

Types

Direct Recursion

A function directly calls itself.

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

The function factorial() calls itself directly until it reaches the base case n == 0.

Indirect/Mutual Recursion

A function calls another function, and the other function calls the first function.

#python code
def functionA(n):
    if n > 0:
        print(n)
        functionB(n - 1)

def functionB(n):
    if n > 1:
        print(n)
        functionA(n // 2)

functionA(5)

functionA() calls functionB(), and functionB() calls functionA().

Tail Recursion

The recursive call is the last statement in the function — nothing is left to do after the call returns.

#python code
def tail_sum(n, total=0):
    if n == 0:
        return total
    return tail_sum(n - 1, total + n)

After the recursive call tail_sum(...), no operation remains — making it a tail-recursive function.

Non-Tail or Head Recursion

The recursive call is not the last statement — some operations happen after the recursive call returns.

#python code
def print_numbers(n):
    if n > 0:
        print_numbers(n - 1)
        print(n)

The recursive call happens first, then printing happens on the way back from recursion — this is non-tail recursion.

Linear Recursion

Each function call results in only one recursive call.

#python code
def countdown(n):
    if n == 0:
        return
    print(n)
    countdown(n - 1)

Each function makes only one recursive call — so it’s linear.

Tree Recursion

A function makes more than one recursive call within itself — forming a recursion tree.

#python code
def fibonacci(n):
    if n <= 1:
        return n
    return fibonacci(n - 1) + fibonacci(n - 2)

Each call to fibonacci() generates two more recursive calls, forming a binary recursion tree.

Nested Recursion

Function calls itself inside its own argument.

#python code
def nested(n):
    if n > 100:
        return n - 10
    return nested(nested(n + 11))

Here, nested(n + 11) is computed recursively before being passed again to nested() — that’s nested recursion.

Problems based on type

Linear Recursion Problems

• Print numbers from 1 to N
• Sum of first N numbers
• Find the factorial of N
• Count digits in a number
• Reverse a string
• Find the maximum element in an array

Tail Recursion Problems

• Sum of numbers using accumulator
• Factorial using accumulator
• Reverse a string using helper parameters

Tree Recursion Problems

• Fibonacci sequence
• Generate all subsets of a set
• Generate all binary strings of length N
• Tower of Hanoi

Indirect / Mutual Recursion Problems

• Print odd/even numbers alternately
• Alternating recursive sequences

Nested Recursion Problems

• Complex math definitions

Non-Tail (Head) Recursion Problems

• Print numbers from 1 to N in ascending order
• Postorder traversal of a tree
• Reverse print of a linked list

Multiple Recursive Patterns

• Merge Sort
• Quick Sort
• Binary Tree Traversal

Summary

Linear
 └─ One call per function (chain)
Tail
 └─ Linear + last operation is recursive call
Non-Tail
 └─ Linear + work happens after recursion
Tree
 └─ Multiple calls per function → branching
Nested
 └─ Function call inside argument of itself
Indirect
 └─ Function A calls B, B calls A (mutual)