MISSION 38

Recursion and Advanced Data Structures

In the previous module, you learned about various data structures such as hash tables and dynamic arrays, and learned the profile of these data structures in terms of their time complexity.

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

As this module progresses, we'll discuss what recursion is, why it's useful, and how to use it to replace loops in your programs (where applicable). You'll learn several important concepts such as recursion, recursive data structures, linked lists, 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. You’ll get to apply what you’ve learned from within your browser — 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.

Objectives

  • Learn how recursion lets us express logic more compactly.
  • Learn how to create recursive algorithms.

Lesson Outline

1. Recursion
2. A Recursive look at Factorials
3. Base Cases
4. Visualization of Recursion
5. Fibonacci
6. Linked Lists - A Recursive Data Structure
7. Exercise: Find the Length of a Linked List
8. Linked List Insertion and Deletion
9. Exercise: Linked List Time Complexity
10. Takeaways

Take a Look Inside