What is recursion? What are its rules? What is it used for?

Recursion is a method of solving a problem where a function calls itself to solve subproblems similar to the original.

Rules of recursion:

• There must be a base (terminal) case, at which point recursive calls stop.
• Each recursive call should approach the base case to avoid infinite recursion.

Why recursion is needed:

• It is convenient for solving problems that naturally break down into similar subproblems (e.g., tree traversal, factorial calculation, Fibonacci numbers).
• It allows writing compact and understandable code for complex data structures and algorithms.

Example of factorial calculation:

function factorial(n) {
  if (n <= 1) return 1; // base case
  return n * factorial(n - 1); // recursive call
}

Recursion is often replaced by iteration if performance is critical or the stack is limited.