Recursion is a powerful programming technique where a function calls itself to solve a problem. It allows complex problems to be broken down into simpler, more manageable . It is built upon three key concepts: , recursive case, and the call stack. The base case is a condition that stops the recursion. It defines the simplest instance of the problem, which can be solved directly without further recursion. If the base case is not defined, the function will call itself indefinitely, leading to a .
The recursive case is the part of the function where the recursion happens. It reduces the problem into smaller and calls the function itself with these smaller inputs. The recursive case must eventually reach the base case. The call stack refers to the data structure that stores information about the active subproblems of a recursive function. Each time a function calls itself, a new frame (or context) is pushed onto the stack. This frame contains important details, including the function's parameters, local variables, and the return of where to return after the function call completes.
When a recursive function is called, a new stack frame is created. Each recursive call adds a new frame to the stack, which continues until a is reached. Once the base case is encountered, the function starts returning values. Each returning function call removes its corresponding frame from the stack, and control goes back to the previous call, which continues execution from where it left off. For example, the function factorial(n) calculates the factorial of a given n by calling itself with decreasing values of n until it reaches the base case.
Keywords
base case | subproblems | base case | subproblems | number | address | stack overflow |
