Recursion and Memoization

Recursive Data Structures

What are recursive data structures, and how are they related to recursive functions?

Abstract art representing computer programming

Recursive data structures are data structures that are defined in terms of themselves. In other words, a recursive data structure contains one or more instances of itself as a part of its own definition. This self-referential nature allows recursive data structures to represent hierarchical or nested relationships efficiently.

Common examples of recursive data structures:

  1. Linked Lists: A linked list is a recursive data structure where each node contains a value and a reference (or pointer) to the next node in the list. The last node typically points to null, indicating the end of the list.
  2. Trees: Trees are recursive data structures composed of nodes, where each node can have zero or more child nodes. The topmost node is called the root, and the nodes at the bottom without any children are called leaves. Examples of trees include binary trees, AVL trees, and B-trees.
  3. Graphs: Graphs can be represented using recursive data structures, where each node (or vertex) contains a value and a list of neighboring nodes (or edges). Graphs can be directed or undirected and can have cycles.

Relationship between recursive data structures and recursive functions: Recursive data structures and recursive functions are closely related. Recursive functions are often used to traverse, manipulate, or process recursive data structures efficiently. The recursive nature of the data structure lends itself well to recursive algorithms.

Here's an example of a recursive function that traverses a binary tree:

#include <iostream>

struct TreeNode {
  int val;
  TreeNode* left;
  TreeNode* right;

  TreeNode(int x)
    : val(x), left(nullptr), right(nullptr) {}

void inorderTraversal(TreeNode* root) {
  if (root == nullptr) {
  std::cout << root->val << " ";

int main() {
  TreeNode* root = new TreeNode(1);
  root->left = new TreeNode(2);
  root->right = new TreeNode(3);
  root->left->left = new TreeNode(4);
  root->left->right = new TreeNode(5);

  std::cout << "Inorder traversal: ";
  std::cout << "\n";

  // Clean up the dynamically allocated memory
  delete root->left->right;
  delete root->left->left;
  delete root->right;
  delete root->left;
  delete root;
Inorder traversal: 4 2 5 1 3

In this example, we define a TreeNode struct that represents a node in a binary tree. Each node contains an integer value (val) and pointers to its left and right child nodes.

The inorderTraversal function is a recursive function that performs an inorder traversal of the binary tree. It follows these steps:

  1. If the current node is null, return (base case).
  2. Recursively traverse the left subtree.
  3. Process the current node (in this case, print its value).
  4. Recursively traverse the right subtree.

By recursively calling inorderTraversal on the left and right child nodes, we can traverse the entire binary tree in a specific order.

The main function demonstrates the creation of a binary tree and the usage of the inorderTraversal function to traverse the tree.

It's important to note that when using recursive data structures with dynamically allocated memory (like in this example), it's crucial to properly clean up the memory to avoid leaks. The code at the end of main demonstrates how to delete the dynamically allocated nodes.

Recursive data structures and recursive functions go hand in hand. The recursive nature of the data structure naturally leads to recursive algorithms for processing and manipulating the data. Recursive functions can elegantly express the traversal and manipulation logic, making the code more concise and easier to understand.

Answers to questions are automatically generated and may not have been reviewed.

A computer programmer
Part of the course:

Professional C++

Comprehensive course covering advanced concepts, and how to use them on large-scale projects.

Free, unlimited access

This course includes:

  • 124 Lessons
  • 550+ Code Samples
  • 96% Positive Reviews
  • Regularly Updated
  • Help and FAQ
Free, Unlimited Access

Professional C++

Comprehensive course covering advanced concepts, and how to use them on large-scale projects.

Screenshot from Warhammer: Total War
Screenshot from Tomb Raider
Screenshot from Jedi: Fallen Order
Contact|Privacy Policy|Terms of Use
Copyright © 2024 - All Rights Reserved