Recursion

Definition

Recursion is a programming technique where a function calls itself to solve smaller instances of the same problem. It typically involves a base case to terminate the recursive calls and prevent infinite loops.

5 Must Know Facts For Your Next Test

1. A recursive function must have a base case that stops the recursion.
2. Each recursive call should progress towards the base case.
3. Stack overflow can occur if there are too many recursive calls without reaching the base case.
4. Recursion can often be replaced with iteration, but recursion is more natural for problems like tree traversal and factorial calculation.
5. Python has a default recursion limit, which can be checked and modified using sys.getrecursionlimit() and sys.setrecursionlimit().

Review Questions

• What is a base case in recursion?
• How does Python handle excessive recursive calls?
• Can all recursive algorithms be converted into iterative ones? Provide an example.

Related terms

Base Case:

The condition under which a recursive function stops calling itself, preventing infinite recursion.

Stack Overflow: An error that occurs when there are too many nested function calls, exhausting the program's stack space.

Iteration:

A programming technique where a set of instructions is repeated in a sequence until a condition is met, often used as an alternative to recursion.