This is the technique of a function calling itself recursively to find an answer and returning at some given condition. This is in opposition to Iterative algorithms that achieve what they want in a for or while loop.

The important thing to remember is to set up a return condition that will always be met otherwise, this could go on forever (see Halting problem ).

# Example

Given a set of single characters $C$ and a length $k$ print all strings of length $k$ using characters from $C$.

from typing import Set

def print_characters_string(
    length: int,
    characters: Set[str],
    previous_string: str
):

    if length <= 0:
        print(previous_string)
        return

    for character in characters:
        print_characters_string(
            length - 1,
            characters,
            previous_string + character
        )

if __name__ == "__main__":
    length = 5
    characters = {"a", "b"}
    print_characters_string(5, characters, '')

# Versions

Recursion can be further classified into different forms.

# Simple (direct) Recursion

In simple or direct recursion, a function calls itself directly but not necessarily as the last operation. It might perform some calculations after the recursive call.

def factorial(step: int):
    if step <= 0:
        return 1
    return step * factorial(step-1)

# Multiple or Tree Recursion

Here, a function calls itself more than once. This creates a tree-like call structure. The Fibonacci sequence is a classic example.

def fibonacci(step:int):
    if step <= 0:
        return 0
    elif step == 1:
        return 1
    return fibonacci(step-1) + fibonacci(step-2)

Note these algorithms are likely to have exponential run time and in the case of the Fibonacci sequence this can be speed up with Dynamic programming instead.

# Tail Recursion

In tail recursion, the recursive call is the last operation in the function. Tail-recursive functions can be easily optimized by compilers or other techniques like Trampolining .

def factorial_tail(step: int, accumulator=1 : int):
    if n == 0:
        return accumulator
    return factorial_tail(n-1, n * accumulator)

# Indirect Recursion

Indirect recursion involves a function A calling another function B, which in turn might call another function C, which eventually leads back to a call to A. Essentially, function A is indirectly calling itself through one or more intermediate function calls.

# Mutual Recursion

This is a subset of indirect recursion, where functions form a call cycle.

def is_even(step: int) -> bool:
	"""
	Returns true if the positive integer is even.
	"""
    if step == 0:
        return True
    return is_not_odd(step - 1)

def is_not_odd(step:int):
	"""
	Returns false if the positive integer is odd.
	"""
    if step == 0:
        return False
    return is_even(step - 1)

# Advantages

Simplicity and Readability: Recursion can make some algorithms simpler and easier to understand. The reduction of complex tasks into simpler sub-tasks can result in more readable code.
Elegant Solutions: Problems that have recursive structures or can be divided into similar sub-problems can be naturally solved with recursion.
Less Code: Recursive methods can lead to shorter code, which is often easier to maintain.
Immutable State: In functional programming, recursion can help maintain immutability , as you don’t need loops and mutable variables.
Easy to Parallelise: Some recursive algorithms are easier to parallelise than their iterative counterparts.
Mathematical Induction: Recursion is a direct implementation of mathematical induction , allowing you to solve problems in a mathematically sound way.

# Limitations

Stack Overflow: Each recursive call adds a new layer to the stack , so if your recursion goes too deep, you risk running out of stack space and causing a stack overflow.
Performance Overheads: Recursive calls can be more expensive than simple loops due to the overhead of maintaining the stack and the function calls.
Memory Usage: Due to the use of the stack to keep track of operations, recursion can be memory-intensive.
Hard to Debug: Recursive functions can sometimes be tricky to debug because of their non-linear execution pattern.
Limited Language Support: Not all languages are optimized for recursion. For example, languages that don’t optimize for tail recursion can run into performance issues for certain problems.
Base Case: Failing to define a base case can result in infinite recursion!
Cognitive Load: For some people, recursion is harder to understand than iteration, adding to the cognitive load of reading or maintaining the code.
Side Effects: In languages that allow side effects , care must be taken to understand how recursive function calls might affect shared state or variables.
Optimization: Some compilers or interpreters may not optimize recursion well, leading to inefficient code.

# Recursion