Algorithm Design Strategies

Recursion is a technique in which a function solves a problem by calling itself on smaller instances of that same problem, relying on a base case that terminates the recursion and a recursive case that reduces the problem toward that base case. Each recursive call adds a new frame to the program's call stack, which means excessively deep recursion risks a stack overflow, though some languages and compilers can optimize a specific pattern called tail recursion to avoid this. Recursion is the natural way to express problems with a self-similar structure, and it forms the conceptual foundation for divide-and-conquer algorithms, for traversing trees and graphs, and for backtracking search.