CodeBlanks Logo Icon CodeBlanks
Login Register

Recursive structure

Divide and conquer is recursive.

Recursive structure

Divide and conquer is built on recursion. Each subproblem is solved by the same function.

The base case stops when the subproblem is small enough to solve directly; this is essential.

Recursion shrinks the problem at each level; complex structures become simple.

Base case

The base case is usually a single-element or empty array. Here the work is done directly, no split.

Without a base case recursion loops forever; the stack overflows and the program crashes.

The base case is the cornerstone of recursive solutions; it must be defined correctly.

Practice Divide and max

Write dc_max(arr). Split in half, find the max of each recursively, return the larger. Print 5 with print(dc_max([3, 1, 4, 1, 5])).

Starter code

solution.py
def dc_max(arr):
    # Divide and find max

Sample solution

solution.py
def dc_max(arr):
    # Divide and find max
    if len(arr) == 1:
        return arr[0]
    mid = len(arr) // 2
    left = dc_max(arr[:mid])
    right = dc_max(arr[mid:])
    return left if left > right else right
print(dc_max([3, 1, 4, 1, 5]))

Expected output

5

Questions and answers

Review the lesson questions together with their answers. To test yourself, solve the lesson interactively.

1 Base condition

Question 
if len(arr) <= ____:
Answer 
if len(arr) <= 1:

Explanation: 1 is right.

2 Recursive structure: match the terms

Term Meaning
base case Stops
recursion Splits
subproblem Subproblem
combine Merges

3 What is the base case's role in divide and conquer?

  • Reduce memory
  • Speed up
  • Stop recursion Correct answer
  • Sort

Explanation: Stop recursion.

All lessons in Intermediate

1 Merge sort

  1. Divide and conquer
  2. Merge operation
  3. Full merge sort
  4. Summary - Merge sort

2 Quick sort

  1. Pivot selection
  2. Partitioning
  3. Recursive quick sort
  4. Summary - Quick sort

3 Heap sort

  1. What is a heap?
  2. Heapify
  3. Build heap and sort
  4. Summary - Heap sort

4 Counting sort

  1. Counting idea
  2. Count array
  3. Output array
  4. Summary - Counting sort

5 Radix sort

  1. Radix idea
  2. Digit pass
  3. Stable sub-sort
  4. Summary - Radix sort

6 Sorting project

  1. Project: Overview
  2. Score array
  3. Apply merge sort
  4. Print statistics

7 Tree

  1. What is a tree?
  2. Node and edge
  3. Binary tree
  4. Summary - Trees

8 Binary search tree

  1. BST rule
  2. BST insert
  3. BST search
  4. Summary - BST

9 AVL tree

  1. Balanced tree
  2. Rotation
  3. Balance after insert
  4. Summary - AVL tree

10 Heap

  1. Min and max heap
  2. Insert
  3. Extract
  4. Summary - Heap

11 Priority queue

  1. What is a priority queue?
  2. Heap-based implementation
  3. Push and pop
  4. Summary - Priority queue

12 Data structures project

  1. Project: Overview
  2. Undo stack
  3. Pending queue
  4. Print the state

13 Graph basics

  1. What is a graph?
  2. Adjacency list
  3. Adjacency matrix
  4. Summary - Graph

14 Breadth-first search

  1. BFS idea
  2. Using a queue
  3. Marking visited
  4. Summary - BFS

15 Depth-first search

  1. DFS idea
  2. Stack or recursion
  3. Backtracking
  4. Summary - DFS

16 Greedy algorithms

  1. Greedy approach
  2. Coin change
  3. Greedy limits
  4. Summary - Greedy

17 Divide and conquer

  1. Three steps
  2. Recursive structure
  3. Master theorem
  4. Summary - Divide and conquer

18 Backtracking

  1. What is backtracking?
  2. State tree
  3. Pruning
  4. Summary - Backtracking

19 Graph project

  1. Project: Overview
  2. City graph
  3. BFS for reachability
  4. Print the result

20 Intermediate final

  1. Challenge 1
  2. Challenge 2
  3. Challenge 3
  4. Challenge 4