Recursion Basics

Introduction to Recursion

• Definition: Recursion occurs when a function calls itself in order to solve a problem.
• Base Case: Critical for recursion; it's the condition under which the recursion ends.

Real-Life Example of Recursion

• Scenario: Inviting friends for lunch.
  • Each friend's response depends on another friend.
  • Ajay serves as the base case; once he responds, all others resolve.

Code Representation of Recursion

• Multiple Functions as Representation: Example of five functions representing five friends calling each other.
• Base Case in Code: Ajay returns a value (true/false) affecting all others accordingly.

Understanding Recursion in Code

Recursive Function Example

• Created a function named recursiveFunction that calls itself.
• Endless Loop: Demonstrates the importance of having a base case to prevent infinite recursion.

Adding a Base Case

• Example of a base case: If a certain condition is met (e.g., reaching the 5th person), return true. The recursion unwinds.

Importance of Recursion

• Used in various algorithms:
  • Tree and graph traversal
  • Sorting algorithms
  • Divide and conquer strategies
  • Backtracking
  • Dynamic programming

Convert Loop to Recursion Example: Multiply Elements in an Array

1. Initial Function with Loop - Multiplies all elements in an array using a loop.
2. Recursive Version:
   • Define function multiply(array) to multiply elements recursively.
   • Base case: If array length is 0, return 1.
   • Use array slicing to reduce size with each call.

Common Recursion Interview Questions

Factorial of n

• Definition: n! = n ( \times (n-1)! )
• Base Case: If n is 0, return 1.

Range of Numbers

• Task: Create an array of numbers from start to end using recursion.
• Base Case: If end number is less than start number, return an empty array.

Palindrome Check

• Definition: A number that reads the same backwards and forwards.
• Example: 121 is a palindrome; 10 is not.

Fibonacci Sequence

• Definition: Each number is the sum of the two preceding ones.
• Base Case: Return n if it is 0 or 1.
• Recursive call: Fibonacci(n-1) + Fibonacci(n-2).

Backtracking Algorithm Example: Subsets

• Task: Generate all possible subsets of an array.
• Approach: For each element, decide to include it or not, leading to a branching structure.
• Base Case: Return the result when the index reaches the length of the array.
• Use temporary array to store current subset and push/pop as needed.

Conclusion

• Recursion is a powerful tool in programming and can simplify code structure and readability.
• Understanding base cases and recursive paths is crucial for mastering recursion.