Skip to content
Gallery
Backend Development | Mid-Track Exam 2 Refresher
Backend Development | Mid-Track Exam 2 Refresher
Share
Explore
Data Structures and Algorithms

Recursion & Backtracking

Recap: Recursion

Understanding Recursion

Definition:
Recursion is when a function calls itself until it meets a base case, preventing stack overflow.
Example:
A function prints "Hello World" repeatedly until a counter hits zero.

Recursive Function Example: Sum of Numbers

Problem:
Calculate the sum of numbers up to N using recursion.
Approach:
Function calls itself with 'n-1' until 'n' is zero, then sums the results.
Comparison: Iterative vs. Recursive:
Iterative: O(N) time, O(1) space.
Recursive: O(N) time, O(N) space due to stack calls.

Benefits of Learning Recursion

Simplifies solving complex problems and aids in understanding dynamic programming.

Nth Fibonacci Number

Problem Description

Fibonacci Series:
Each number is the sum of the two preceding ones, starting with 0 and 1.

Recursive Approach

Function Definition:
Base cases for 0 and 1, recursive calls for others.
Complexity Analysis:
Time Complexity: O(2^N).
Space Complexity: O(N) due to recursion stack.

Subsequence Generation Using Recursion

Understanding Subarrays and Subsequences

Subarray: Contiguous part of an array.
Subsequence: Maintains order but can be non-contiguous.

Generating Subsequences

Take or Not Take Approach:
Decide to include or exclude each element.
Implementation:
Recursive calls to include/exclude elements, printing subsequences at the base case.
Complexity Analysis:
Time Complexity: O(2^N).
Space Complexity: O(N).
For more detailed information, refer to the Notion link:
Recursion & Backtracking
⁠
⁠
Want to print your doc?
This is not the way.
Try clicking the ⋯ next to your doc name or using a keyboard shortcut (
CtrlP
) instead.