In the past few courses, you have been learning about different data structures and their respective algorithms. We have been describing how to efficiently search and update these structures, but there has always been a trade-off between the two. In this course, we will be developing a data structure that will have both fast search and efficient updates. Additionally, this course will cover recursion and trees.

In this lesson, you'll learn about a basic mechanism that has given rise to many interesting data structures and algorithms: recursion. Throughout this lesson, you will learn what recursion is and how to implement it in your programming. Recursion doesn't always deal with algorithms, it is also used in data structures such as linked lists and binary trees.

As this lesson progresses, we'll discuss what recursion is, how to think about recursion, why it's useful, additional algorithms, and more! Along the way, you'll learn about important related concepts like recursive data structures, merge sort, and more!

Recursion can be a difficult concept to grasp at first, but it's a very rewarding and fun tool once you understand it. Because it's difficult to grasp without any hands-on practice, you’ll get to apply what you’ve learned from within your browser so that there's no need to use your own machine to do the exercises. The Python environment inside of this course includes answer checking so you can ensure that you've fully mastered each concept before learning the next concept.


  • Learn the difference between iteration and recursion.
  • Learn what type of problems are best suited for recursion.
  • Learn how recursion can describe a tree structure.

Lesson Outline

1. Introduction
2. Recursion is thinking in Recursion
3. Stack Overflow
4. Divide and Conquer
5. Merge Sort (Part 1)
6. Merge Sort (Part 2)
7. Analysis of Merge Sort
8. Next Steps
9. Takeaways