Recursion

Recursion is an approach to problem solving where the solution depends partially on solutions to smaller instances of related problems.

A recursive function consists of base cases and calls to the same function with different arguments. Two key ingredients to a successful use of recursion are identifying the base cases, which are to be solved directly, and ensuring progress, that is the recursion converges to the solution.

Question to ask yourself when solving a recursion question

1. What is the base case ? i.e. A stopping condition that allows you stop a recursive program or function

2. What is the least amount of work I can do in each Iteration (function call)

Pros for using Recursion

1. Bridges the gap between elegance and complexity
2. Reduces the need for complex loops and auxilliary data structures
3. Can reduce time easily with memoization
4. Works really well with recursive data structures like trees & Graphs

Cons for using Recursion

1. Slowness due to CPU Overload
2. Can lead to out of memory errors / Stack overflow exceptions
3. Can be unnecessarily complex if poorly constructed

Questions

In this section we will solve common recursion questions that will help you understand the basics of recursion

• Recursion With Strings
  • Reverse String
  • Palindrome
• Recursion With Numbers
  • Decimal To Binary
  • Sum Of Natural Numbers
• Divide & Conquer
  • Fibonacci
  • Binary Search
  • Merge Sort 1
  • Merge Sort 2
  • Reverse Linkedlist
  • Merge Two Sorted List
  • Insert Into Binary Search Tree
  • Get Leaf Nodes
  • Depth First Search

References

▶ Recursion in Programming - Full Course