Table of Content
Recap: Recursion
Understanding Recursion
- Definition:
- Recursion is a process where a function calls itself until it meets a specific condition (base case) and then returns to the point where it started.
- Without a base case, recursion can lead to a stack overflow error.
- Example:
- A function that prints "Hello World" repeatedly.
- Adding a base case with a decrementing counter to stop recursion after a certain number of calls.
- Dry Run Example:
- A function that prints "Hello World" 10 times.
- The function checks if the counter is zero; if not, it prints the message, decrements the counter, and calls itself again.
- The process continues until the counter reaches zero.
Recursive Function Example: Sum of Numbers
Benefits of Learning Recursion
Nth Fibonacci Number
Problem Description
- Fibonacci Series:
- A sequence where each number is the sum of the two preceding ones.
- First two numbers are 0 and 1.
Recursive Approach
- Function Definition:
- Create a function that takes an integer 'n' and returns the Nth Fibonacci number.
- Add base cases for the first and second Fibonacci numbers (0 and 1).
- For other cases, return the sum of the previous two Fibonacci numbers.
- Dry Run Example:
- To find the 5th Fibonacci number, the function will call itself with values 5, 4, 3, 2, and 1.
- Base cases return 0 and 1, and the function adds up the values as it returns from each recursive call.
- Final result for the 5th Fibonacci number is 3.
- Complexity Analysis:
- Time Complexity: O(2^N) due to the exponential growth of recursive calls.
- Space Complexity: O(N) due to the depth of the recursion stack.
Subsequence Generation Using Recursion
Understanding Subarrays and Subsequences
- Subarray:
- A contiguous part of an array.
- Elements appear in sequence without gaps.
- Subsequence:
- Can be contiguous or non-contiguous but maintains the order of elements.
- Examples: For array [6, 7, 2], subsequences include [], [6], [7], [2], [6, 7], [7, 2], [6, 2], [6, 7, 2].