Recursion is an approach to problem solving when a problem can be broken down to smaller tasks that can be performed repetitively to achieve the stated objective. However, it needs to be understood wisely before using it.
Use the following framework to identify how to solve problems using recursion:
- In what ways can be problem be broken down into smaller problems
- Identify the smallest possible problem and how a (trivial) solution can be obtained.
Implement the solution to the smallest possible problem. [aka the base case]
- Assume that the smaller problem is solved. How will you solve the bigger problem now.
Implement the solution.
These three steps are: Divide, Conquer, Combine
Recursive approaches are in direct competition with loops. The choice between recursion and loops boils down the 3 key considerations:
- Nature of problem
- Performance requirements
- Code readability
Overall, choose loops for performance-critical, memory-constrained, or straightforward repetitive tasks, especially in languages or environments without efficient recursion support
Determining space efficiency of recursion:
The key concept to understand is the concept of the call stack.
In essence, the call stack is where all functions go when they are being executed. All their local variables are in the stack.
During recursion of depth n, n copies of the function are in the call stack. To analyze the space complexity of a recursive algorithm, we consider the maximum depth of the recursive calls, as it determines the space used by the call stack.
Complexity = Depth x Space used by each entry in the call stack
Recursion is usually not an efficient way to come up with a solution. However, there exist, famous efficient, recursive solutions for difficult problems. Notably, these include:
- The Karatsuba Algorithm for integer multiplication
- Strassen’s matrix multiplication algorithm
- Closest pair problem (see https://sites.cs.ucsb.edu/~suri/cs235/ClosestPair.pdf)
This is a masterful use of recursion to reduce the computational complexity of a \(O(N^2)\) problem.
- Merge Sort
- Binary Search
One principle behind making recursive algorithms more efficient is by saving recursive calls. Saving one call means that it is safe over and over again, so the savings are compounded. This results in an asymptotically superior running time. This is why the first two algorithms in the list are remarkably efficient.