✦ScienexySCIENCE KNOWLEDGE LIBRARY
concept · INFO-CS-ADS-144

Introduction to Recursion

Recursion is a programming technique in which a function solves a problem by calling itself with a smaller or simpler version of the original problem. It is especially useful when a problem can naturally be divided into similar subproblems, such as traversing trees, processing nested structures, and solving divide-and-conquer algorithms.

Explanation

Overview

A recursive function is a function that directly or indirectly invokes itself during its execution. Each recursive call works with a modified input or a smaller portion of the problem until a stopping condition is reached.

Core idea

Instead of solving every part of a problem in one sequence of instructions, recursion repeatedly applies the same solution strategy to progressively smaller subproblems.

How it works

A program calls a recursive function with an initial input.; The function checks whether the input satisfies the base case.; If the base case is not satisfied, the function performs any required work and makes another recursive call.; Each call receives a smaller or simpler problem.; Eventually, a call reaches the base case and returns a result.; The pending calls resume in reverse order as their results are returned.

Time complexity

There is no single time complexity for recursion itself. Complexity depends on the number of recursive calls and the amount of work performed in each call. The factorial example performs n + 1 calls and takes O(n) time.

Space complexity

Recursive calls generally require call-stack memory. The factorial example has a maximum recursion depth of O(n), so its auxiliary stack space is O(n).

Advantages

Produces concise solutions for naturally recursive problems.; Matches the structure of trees, nested data, and mathematical definitions.; Makes divide-and-conquer algorithms easier to express.; Can simplify complex search and backtracking logic.

Limitations

Deep recursion can cause a stack overflow or recursion-depth error.; Function-call overhead can make recursion slower than an equivalent loop.; Recursive solutions may use more memory than iterative solutions.; Poorly designed recursion can repeat calculations unnecessarily.; Missing or incorrect base cases can cause non-terminating recursion.

Example or application

A worked example has not yet been added.

Definition

A recursive function is a function that directly or indirectly invokes itself during its execution. Each recursive call works with a modified input or a smaller portion of the problem until a stopping condition is reached.

Core Idea

Instead of solving every part of a problem in one sequence of instructions, recursion repeatedly applies the same solution strategy to progressively smaller subproblems.

Main Components

NameDescription

Base case

The condition that stops further recursive calls and provides a direct result.

Recursive case

The part of the function that calls itself with a smaller or simpler input.

Progress toward termination

The input must move closer to a base case with every recursive call.

How It Works

  • A program calls a recursive function with an initial input.

  • The function checks whether the input satisfies the base case.

  • If the base case is not satisfied, the function performs any required work and makes another recursive call.

  • Each call receives a smaller or simpler problem.

  • Eventually, a call reaches the base case and returns a result.

  • The pending calls resume in reverse order as their results are returned.

Simple Example

Problem

Calculate the factorial of a non-negative integer.

Mathematical Definition

n! = n × (n - 1)! for n > 0, and 0! = 1.

Python Code

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

print(factorial(5))

Output

120

Explanation

  • factorial(5) calls 5 × factorial(4).

  • factorial(4) calls 4 × factorial(3).

  • The calls continue until factorial(0) returns 1.

  • The pending multiplications then produce 1 × 1 × 2 × 3 × 4 × 5 = 120.

Recursive Call Sequence

  • factorial(5)

  • 5 × factorial(4)

  • 5 × 4 × factorial(3)

  • 5 × 4 × 3 × factorial(2)

  • 5 × 4 × 3 × 2 × factorial(1)

  • 5 × 4 × 3 × 2 × 1 × factorial(0)

  • Return value: 120

Common Applications

  • Calculating factorials and mathematical sequences.

  • Traversing binary trees and other hierarchical structures.

  • Searching through nested folders and directories.

  • Implementing merge sort and quicksort.

  • Solving maze and path-finding problems.

  • Processing nested expressions and data structures.

  • Generating combinations and permutations.

Time Complexity

There is no single time complexity for recursion itself. Complexity depends on the number of recursive calls and the amount of work performed in each call. The factorial example performs n + 1 calls and takes O(n) time.

Space Complexity

Recursive calls generally require call-stack memory. The factorial example has a maximum recursion depth of O(n), so its auxiliary stack space is O(n).

Advantages

  • Produces concise solutions for naturally recursive problems.

  • Matches the structure of trees, nested data, and mathematical definitions.

  • Makes divide-and-conquer algorithms easier to express.

  • Can simplify complex search and backtracking logic.

Limitations

  • Deep recursion can cause a stack overflow or recursion-depth error.

  • Function-call overhead can make recursion slower than an equivalent loop.

  • Recursive solutions may use more memory than iterative solutions.

  • Poorly designed recursion can repeat calculations unnecessarily.

  • Missing or incorrect base cases can cause non-terminating recursion.

Implementation Guidelines

  • Identify the smallest problem that can be solved directly.

  • Define a clear base case before writing the recursive case.

  • Ensure every recursive call moves closer to termination.

  • Determine what each call returns to its caller.

  • Estimate maximum recursion depth and memory requirements.

  • Consider memoization when overlapping subproblems cause repeated work.

Common Mistakes

  • Forgetting to define a base case.

  • Writing a recursive call that does not reduce the problem.

  • Using the wrong return expression.

  • Assuming recursive calls execute simultaneously.

  • Ignoring the memory consumed by the call stack.

  • Recomputing the same subproblem without caching its result.

Learning Tip

Trace a recursive function manually using a small input, such as factorial(3). Write down every function call and return value separately. Understanding the order of calls and returns is more important than memorizing recursive code.

Practice Questions

QuestionAnswer

What is the main purpose of introduction to recursion?

Recursion is a programming technique in which a function solves a problem by calling itself with a smaller or simpler version of the original problem. It is especially useful when a problem can naturally be divided into similar subproblems, such as traversing trees, processing nested structures, and solving divide-and-conquer algorithms.

What should be checked before applying introduction to recursion?

For introduction to recursion, verify the stated inputs, assumptions, expected result, boundary cases, and time and memory constraints.

How can an implementation of introduction to recursion be validated?

Trace a representative introduction to recursion case manually, test its boundary conditions, and compare the result with the specification or a trusted baseline.

Learning Objectives

  • Explain the central idea and purpose of introduction to recursion.

  • Identify the assumptions, inputs, and conditions relevant to introduction to recursion.

  • Evaluate an application of introduction to recursion for correctness and practical resource requirements.

Sources and verification

Sources are shown as provided in the project data. Not every source has yet been independently verified. Please report errors or missing citations.

  • Scienexy Computer Science Reference

Suggest a correction or source · More in Algorithms & Data Structures