ZeroToSky
Data Structures and Algorithms Tutorial 15 of 486
Foundations 17/41
Fundamentals

All 13 lessons →

Maths, Pattern & Recursion

All 28 lessons →

Core Data Structures 0/224
Array & String
  • Array Basics
  • String Basics
  • Matrix Basics
  • Is Sorted
  • Multiply with Adjacent
  • Reverse Array
  • Reverse in Groups
  • Rotate Array
  • Generate All Subarrays
  • Arrange by Sign
  • Stock Buy/Sell - One Transaction
  • Stock Buy/Sell - Multiple Transactions
  • Leaders in Array
  • Same Strings
  • Palindrome String
  • Toggle Case
  • Remove Occurrences
  • Remove Spaces
  • Check Subsequence
  • First Non-Repeating Character
  • Pangram
  • Majority Element
  • Majority Element II
  • Sorted Subsequence of 3
  • Count Strictly Increasing Subarrays
  • Next Permutation
  • Kadane's Algorithm
  • Sum of All Subarrays
  • Maximum Product Subarray
  • Implement atoi
  • URLify
  • Multiply Large Numbers
  • Diagonal Traversal
  • Magic Square
  • Boundary Traversal
  • Spiral Matrix
  • Toeplitz Matrix
  • Matrix Zig-Zag
  • Transpose of Matrix
  • Rotate Matrix by 90 Degrees
  • Conway's Game of Life
  • Queries in a Matrix
  • Set Matrix Zeroes
  • Maximum Circular Subarray Sum
  • Next Smallest Palindrome
  • Lexicographic Rank
  • Text Justification

All 47 lessons →

Linked List
  • Linked List Basics
  • Singly Linked List
  • Doubly Linked List
  • Circular Linked List
  • Reverse Singly Linked List
  • Reverse Doubly Linked List
  • Reverse in Groups
  • Reorder List
  • Find Middle
  • Remove Nth From End
  • Check Palindrome
  • Detect Cycle
  • Intersection of Y-Shaped Lists
  • Sort 0s 1s 2s
  • Add Two Numbers
  • Merge K Sorted Lists
  • Browser History
  • Twitter Design
  • LRU Cache
  • LFU Cache
  • Flatten Linked List
  • Clone Linked List With Random Pointer

All 22 lessons →

Stack
  • Stack Basics
  • Reverse Stack
  • Sort Stack
  • Balanced Parentheses
  • Postfix Evaluation
  • Infix Evaluation
  • Infix to Postfix
  • Redundant Brackets
  • Longest Valid Parentheses
  • Stack Using Queues
  • Two Stacks in an Array
  • K Stacks in an Array
  • Stack With getMin
  • Remove K Digits
  • Next Greater Element
  • Stock Span Problem
  • Previous Smaller Element
  • Largest Rectangle in Histogram
  • Trapping Rain Water
  • Decode String

All 20 lessons →

Queue
  • Queue Basics
  • Circular Queue
  • Queue Using Stacks
  • FIFO Page Replacement
  • Reverse a Queue
  • Reverse First K Elements
  • Interleave Queue
  • K Queues in an Array
  • First Non-Repeating Character in a Stream
  • Minimum Knight Steps

All 10 lessons →

Deque
  • Deque Basics
  • Circular Array Implementation
  • Lexicographically Largest Permutation
  • Generate Bitonic Sequence
  • Sliding Window Maximum
  • Longest Subarray With Difference <= X
  • Minimum Deques to Sort Array

All 7 lessons →

Hashing
  • Hashing Basics
  • Linear Probing
  • Separate Chaining
  • Quadratic Probing
  • Distinct in Array
  • Is Subset
  • Union of Arrays
  • Intersection of Arrays
  • Two Sum
  • Fizz Buzz
  • Pair Sums Divisible by K
  • Roman to Integer
  • Isomorphic Strings
  • Count Frequencies
  • Most Frequent Element
  • Maximum Subsets
  • Anagrams
  • Longest Consecutive Subsequence
  • Consecutive Subsequence

All 19 lessons →

Heap
  • Heap Basics
  • Check for Heap
  • Heap Sort
  • Kth Largest
  • K Largest Elements
  • Height of Heap
  • Connect N Ropes
  • Nearly Sorted Array
  • BST to Min Heap
  • K Max Sum Combinations
  • Median in a Stream
  • Kth Largest in a Stream
  • Merge K Sorted Arrays/Lists
  • Range Covering K Sorted Lists
  • Skyline Problem
  • Sort by Frequency

All 16 lessons →

Binary Tree
  • Binary Tree Basics
  • Inorder Traversal
  • Preorder Traversal
  • Postorder Traversal
  • Level Order Traversal
  • Size of Tree
  • Depth of Tree
  • Maximum Width
  • Check Balanced Tree
  • Identical Trees
  • Mirror Tree
  • Sum Tree
  • Left View
  • Right View
  • Path Sum
  • Maximum Path Sum
  • Serialize and Deserialize
  • Iterative Inorder
  • Iterative Preorder
  • Iterative Postorder
  • Morris Inorder
  • Diameter of Tree
  • Boundary Traversal
  • Tree From Preorder and Inorder
  • Connect Nodes at Same Level
  • Invert Tree
  • Flatten Tree
  • Vertical Traversal
  • Bottom View
  • Top View
  • Spiral Level Order
  • Lowest Common Ancestor
  • Distance K
  • Subtree Check

All 34 lessons →

Binary Search Tree
  • BST Basics
  • Search in BST
  • Insert in BST
  • Delete in BST
  • Ceil in BST
  • Floor in BST
  • Predecessor and Successor
  • Kth Smallest Element
  • Two Sum in BST
  • Sorted Array to BST
  • Merge Two BSTs
  • Validate BST
  • Lowest Common Ancestor
  • Recover BST
  • Largest BST Subtree

All 15 lessons →

Trie
  • Implement Trie
  • Longest Word With All Prefixes
  • Count Distinct Substrings
  • Maximum XOR of Two Numbers
  • Maximum XOR Queries
  • Pairs With XOR Less Than K
  • Search Suggestions System
  • Palindrome Pairs

All 8 lessons →

Graph
  • Graph Representation
  • BFS Traversal
  • DFS Traversal
  • Flood Fill
  • Number of Islands
  • Connected Components in Undirected Graph
  • Cycle in Undirected Graph
  • Cycle in Directed Graph
  • Bipartite Graph
  • Rotten Oranges
  • Topological Sort
  • Course Schedule I
  • Course Schedule II
  • Alien Dictionary
  • Dijkstra's Algorithm
  • Floyd Warshall
  • Bellman-Ford
  • Minimum Cost Path
  • Shortest Cycle in Undirected Graph
  • Distance of Nearest 1
  • Word Ladder
  • Prim's Algorithm
  • Disjoint Set Union
  • Kruskal's Algorithm
  • Detect Cycle Using DSU
  • Number of Connected Components

All 26 lessons →

Problem-Solving Patterns 0/99
Two-Pointer
  • Two-Pointer Technique
  • Two Sum in Sorted Array
  • Smallest Subarray
  • Unique Elements
  • Sentence Palindrome
  • Three Sum
  • Celebrity Problem
  • Closest Pair from Two Arrays
  • Container With Most Water
  • Common Elements in Three Arrays
  • Reverse Words
  • Four Sum
  • Closest Triplet
  • Count Triplets

All 14 lessons →

Sliding Window
  • Sliding Window Technique
  • Maximum Sum Subarray of Size K
  • Maximum XOR of K Size
  • Distinct in Every Window
  • MEX of Subarrays
  • Minimum Swaps to Group All 1s
  • First Negative in Every Window
  • Chocolate Distribution
  • Maximize Ones
  • Equal Substring With Cost <= K
  • Fruit Into Baskets
  • Subarray With Given Sum
  • Smallest Subarray With Sum Greater Than X
  • Minimum Window Subsequence
  • Minimum Window Substring
  • Subarrays With K Odds
  • Subarrays Less Than K
  • Longest Substring With Distinct Characters
  • Longest Substring With K Unique Characters
  • Count Anagrams

All 20 lessons →

Prefix Sum
  • Prefix Sum Basics
  • Prefix Sum Array
  • 2D Prefix Sum
  • Range Queries
  • Equilibrium Index
  • Product of Array Except Self
  • Difference Array
  • 2D Difference Array
  • Subarray With Zero Sum
  • Largest Subarray With Zero Sum
  • Largest Subarray With Equal 0s and 1s
  • Longest Subarray With Sum K
  • Count Subarrays With Sum K
  • Count Subarrays With Given XOR

All 14 lessons →

Bit Manipulation
  • Bit Manipulation Basics
  • Swap Without Third Variable
  • Kth Set Bit
  • Only Set Bit
  • Power of Two
  • Sort by Set Bits
  • Power of Four
  • Binary Palindrome
  • Rotate Bits
  • Swap Odd and Even Bits
  • Count Set Bits
  • Count Total Set Bits
  • Maximum Consecutive 1s
  • Missing Number
  • One Odd Occurring
  • Two Odd Occurring
  • Missing and Repeating
  • Unique Numbers II
  • Gray Codes
  • Hamming Distance
  • Sum of Pair XORs
  • Sum of Subset XORs
  • Subarray XORs
  • Subsets
  • Subsequences

All 25 lessons →

Backtracking
  • Backtracking Basics
  • Permutations
  • Rat in a Maze
  • Word Search
  • N-Queen Problem
  • Sudoku Solver
  • Word Break
  • Knight's Tour
  • Palindromic Partitions
  • M-Coloring

All 10 lessons →

Greedy
  • Greedy Algorithm Basics
  • Fractional Knapsack
  • Assign Cookies
  • Smallest Subset With Greater Sum
  • Minimum Notes With Given Sum
  • Activity Selection
  • Huffman Coding
  • Jump Game
  • Job Sequencing
  • Non-Overlapping Intervals
  • Gas Station
  • Stable Marriage
  • Minimize Maximum Height Difference
  • No Two Adjacent Same
  • Minimize Cash Flow
  • Min Time to Finish Jobs With Constraints

All 16 lessons →

Core Algorithms 0/122
Searching
  • Searching Basics
  • Largest Element
  • Second Largest
  • Local Min and Max
  • Search Insert Position
  • Lower Bound
  • Upper Bound
  • Single Element in Sorted Array
  • Missing Natural Number
  • Count Occurrences
  • Search in 2D Matrix
  • Search in Sorted and Rotated Array
  • Search in Sorted and Rotated Array II
  • K Closest Elements
  • Search in Almost Sorted Array
  • Peak Element
  • Peak Element in 2D
  • Range Based Counts
  • Kth Missing Positive
  • Search in Row-Column Sorted Matrix
  • Square Root
  • Nth Root
  • Check Power
  • Book Allocation
  • Koko Eating Bananas
  • Aggressive Cows
  • Median in Row Sorted Matrix
  • Kth Smallest in Row and Column Sorted Matrix
  • M Bouquets
  • Kth in Multiplication Table
  • Median of Two Sorted Arrays
  • Kth Element of Two Sorted Arrays

All 32 lessons →

Sorting
  • Sorting Basics
  • Wave Form
  • Sort by Length
  • Minimum Difference Pair
  • Merge Overlapping Intervals
  • Form Largest Number
  • Meeting Rooms
  • Insert and Merge Intervals
  • Minimize Moves
  • Quick Sort
  • Sort Binary Array
  • Move Zeroes to End
  • Sort Ternary Array
  • Merge Sort
  • Union of Two Sorted Arrays
  • Intersection of Two Sorted Arrays
  • Merge Without Extra Space
  • Minimum Platforms
  • Inversion Count
  • Cycle Sort
  • Minimum Missing Positive
  • Minimum Swaps to Sort

All 22 lessons →

Dynamic Programming
  • Dynamic Programming Basics
  • Climbing Stairs
  • Count Without Consecutive 1s
  • Frog Jump
  • House Robber
  • Maximum Segments
  • Coin Change
  • Decode Ways
  • Word Break
  • Unique Paths
  • Minimum Cost Path
  • Longest Common Subsequence
  • Edit Distance
  • Distinct Subsequences
  • Largest Square Submatrix of 1s
  • Partition Equal Subset Sum
  • Subset Sum
  • Count Subsets With Given Sum
  • Target Sum
  • 0/1 Knapsack
  • Coin Change II
  • Rod Cutting
  • Unique Paths in a Grid
  • Maximum Path Sum in Matrix
  • Longest Increasing Path
  • Longest Common Substring
  • Shortest Common Supersequence
  • Interleaving String
  • Wildcard Matching
  • Longest Palindromic Substring
  • Buy/Sell With Cooldown
  • Buy/Sell With At Most Two Transactions
  • Buy/Sell With K Transactions
  • Buy/Sell With Transaction Fee
  • Longest Increasing Subsequence
  • Number of LIS
  • Longest Bitonic Subsequence
  • Longest String Chain
  • Matrix Chain Multiplication
  • Minimum Cost to Cut a Stick
  • Palindrome Partitioning
  • Boolean Parenthesization
  • Partition Array for Maximum Sum
  • Egg Dropping

All 44 lessons →

String Matching
  • Substring Search
  • Rabin-Karp
  • KMP Algorithm
  • Z Algorithm
  • Longest Prefix Suffix
  • Manacher's Algorithm
  • Longest Palindromic Substring
  • Palindrome Substring Queries
  • Minimum Repeats for Substring

All 9 lessons →

Number Theory
  • nCr
  • Euler's Totient
  • Sieve of Eratosthenes
  • Pascal's Triangle
  • Modular Exponentiation
  • Segmented Sieve

All 6 lessons →

Range Query
  • Segment Tree
  • Min-Max Range Queries
  • Range LCM Queries
  • Range XOR Queries
  • Lazy Propagation
  • Flipping Sign
  • Segment Tree on N-ary Rooted Tree
  • Fenwick Tree
  • Sum and Update Queries on 3D Matrix

All 9 lessons →

Analysis of Recursion

Learn how to analyze recursive algorithms by counting recursive calls, determining time complexity, and calculating recursion stack space.

Gaurav 3 min read Sign in to save
On this page

Analysis of Recursion in DSA

Analyzing a recursive algorithm means determining how many operations it performs and how much memory the recursive calls use.

The two main factors are:

  • Time Complexity — total work performed by all recursive calls.
  • Space Complexity — memory used by the recursive call stack.

1. Analyze the Base Case

First, identify when recursion stops.

int count(int n) {
    if (n == 0)
        return 0;

    return count(n - 1);
}

The recursion stops when:

n = 0

2. Count Recursive Calls

Consider:

void print(int n) {
    if (n == 0)
        return;

    printf("%d ", n);
    print(n - 1);
}

For n = 5:

print(5)
 → print(4)
   → print(3)
     → print(2)
       → print(1)
         → print(0)

There are approximately n recursive calls.

Therefore:

Time Complexity: O(n)

3. Recursion With Constant Work

If every recursive call performs constant work:

void function(int n) {
    if (n == 0)
        return;

    printf("%d", n);
    function(n - 1);
}

There are n calls and each call performs O(1) work.

Therefore:

Time = O(n)

4. Recursive Call Stack

Each recursive call creates a stack frame.

For:

function(4);

the stack can look like:

function(4)
function(3)
function(2)
function(1)
function(0)

The maximum number of active calls is proportional to n.

Therefore:

Space Complexity = O(n)

This is auxiliary stack space, not the input storage itself.

5. Multiple Recursive Calls

Consider:

int fibonacci(int n) {
    if (n <= 1)
        return n;

    return fibonacci(n - 1) + fibonacci(n - 2);
}

Each call can create two more recursive calls.

The call structure grows rapidly:

                fib(n)
              /        \
        fib(n-1)       fib(n-2)
        /    \          /    \
       ...   ...       ...   ...

The number of calls grows exponentially.

For the simple recursive Fibonacci implementation:

Time Complexity: O(2^n)
Space Complexity: O(n)

The space is O(n) because the deepest active call chain has length proportional to n.

6. Recurrence Relation

A recurrence relation describes the running time of a recursive algorithm in terms of smaller inputs.

For a function making one recursive call:

T(n) = T(n - 1) + O(1)

This gives:

T(n) = O(n)

For a function making two calls:

T(n) = T(n - 1) + T(n - 2) + O(1)

The solution grows exponentially.

Recurrence relations are especially useful for analyzing recursive algorithms such as merge sort, quicksort, and divide-and-conquer algorithms.

7. Divide and Conquer

Consider an algorithm that divides the problem into two halves:

T(n) = 2T(n/2) + O(n)

This recurrence corresponds to algorithms such as merge sort.

Its time complexity is:

O(n log n)

The important point is that recursive analysis depends on:

  • Number of recursive calls
  • Size of each subproblem
  • Work performed outside recursive calls

Common Patterns

Recursive Pattern Typical Complexity
T(n) = T(n-1) + O(1) O(n)
T(n) = T(n/2) + O(1) O(log n)
T(n) = 2T(n/2) + O(n) O(n log n)
T(n) = 2T(n-1) + O(1) O(2^n)

These are common patterns, but the exact complexity should always be derived from the actual algorithm.

Common Mistakes

Counting Only One Recursive Call

When a function makes multiple recursive calls, all of them contribute to the total running time.

Ignoring Work Outside Recursion

This:

printf("%d", n);
function(n - 1);

contains both recursive work and constant work.

Confusing Time and Stack Space

An algorithm can have:

Time:  O(2^n)
Space: O(n)

as in the simple recursive Fibonacci implementation.

Assuming Every Recursion Is O(n)

The complexity depends on how the input changes and how many recursive calls are made.

Quick Analysis Checklist

When analyzing recursion, ask:

  1. What is the base case?
  2. How many recursive calls are made?
  3. How does the input size change?
  4. What work happens outside the recursive calls?
  5. What is the maximum recursion depth?
  6. What recurrence relation represents the running time?

Key Takeaways

  • Analyze recursion by counting calls and work per call.
  • A single call reducing n by one commonly gives O(n) time.
  • Halving the input at each step commonly gives O(log n).
  • Multiple recursive calls can produce exponential complexity.
  • Recursion depth determines stack space.
  • Recurrence relations are useful for analyzing complex recursive algorithms.

Practice Questions

  1. Find the time and space complexity of a recursive function that decreases n by 1.
  2. Analyze a recursive function that divides n by 2.
  3. Find the complexity of recursive Fibonacci.
  4. Analyze the recurrence T(n) = 2T(n/2) + O(n).
  5. Determine the recursion depth of a given recursive algorithm.

What's Next?

Next, learn Recursion Patterns to recognize common recursive structures and apply them to DSA problems.

dsa recurrence recursion recursion-tree space complexity time complexity

Related

Found a problem on this page, or something that could be clearer?

Goes straight to the author. Not published anywhere.