Stacks follow the Last-In-First-Out (LIFO) principle (like a magazine of bullets). Insertions and deletions occur only at the top of the stack. A common application is the implementation of recursive calls.

Queues follow the First-In-First-Out (FIFO) principle (like a line for a COVID test). Insertions occur at the rear and deletions occur at the front.

Sequential storage is more common for both stacks and queues.

Stack

• Stacks grow towards lower memory addresses.
• Stacks cannot be traversed because only the top element is accessible.
• The stack size is determined by a counter that increments with each push operation.

Common Stack Functions

If elements a and b are adjacent, b must be to the left of a. If elements b and c are adjacent, c must be to the left of b.

Recursion

Recursion utilizes the stack. The process of pushing and popping frames helps understand the LIFO behavior.

The Idea of Recursion

The fundamantal idea of recursion is that a function calls itself, either directly or indirectly. This transforms the original problem into smaller sub-problems of the same type. The focus is on how to break down the original problem into valid sub-problems, rather than on how the sub-problems are solved in detail.

Disadvantages of Recursion

Recursion relies on the call stack. Each function call adds a stack frame, and each return removes one. Since the stack has a limited size, excessive recursion depth causes a stack overflow. Recursion can be efficient (e.g., merge sort) or inefficient (e.g., counting hairs on a monkey), as it consumes extra space for the stack, unlike simple iteration.

Characteristics of Recursive Programs

• Elegance: Compared to iterative solutions, recursion often requires fewer lines of code and is easier to understand. The power of recursion lies in defining an infinite set of objects with finite statements.

• Reversal: Recursive programs are well-suited for reversal tasks because they inherently use a stack (LIFO). Examples include reversing strings or linked lists.

• Recurrence Relation: Recursive programs often expose a recurrence relation (f(n) can be expressed in terms of f(n-1), f(n-2), etc.). Problems with recurrence relations can typically be solved recursively. Examples include Pascal's triangle and factorial calculation.

When to Use Recursion

Consider recursion for problems with these characteristics:

• The problem and its sub-problems have a recurrence relation.
• The data structure has a recursive nature (e.g., linked lists, trees, graphs).
• The problem involves a reversal operation.
• Fundamentally, the problem can be broken down layer by layer into minimal, solvable units.

Writing Recursive Code

1. Termination Condition: Determine the condition under which the recursion stops (e.g., n == 1 for factorial, or node == nullptr for tree traversal).
2. Non-recursive Part: Determine what happens in a single, non-recursive step (e.g., adding a single node's data to a vector).
3. Recursive Logic: Determine how to break the problem into smaller, similar sub-problems (e.g., factorial(n) = n * factorial(n-1), or traversing the left and right subtrees of a binary tree).

Note: Steps 2 and 3 can sometimes be reversed, and step 2 may be optional.

Example: Preorder Traversal of a Binary Tree

First, define the tree node:

struct Node {
    int data_;
    Node* left;
    Node* right;
    Node(int data) : data_(data), left(nullptr), right(nullptr) {}
};

Termination Condition: The traversal stops when the tree is empty (node is nullptr).

if (node == nullptr) {
    return;
}

Non-recursive Part: If there is only one node, simply add it to the container.

vec.push_back(node->data_);

Recursive Logic: Traverse the whole tree by: 1) adding the root node to the container, 2) recursively traversing the left subtree, and 3) recursively traversing the right subtree.

frontfind(node->left, vec);
frontfind(node->right, vec);

Complete Code:

void frontfind(Node* node, vector<int>& vec) {
    if (node == nullptr) {
        return;
    }
    vec.push_back(node->data_);
    frontfind(node->left, vec);
    frontfind(node->right, vec);
}

Execution Logic:

Inorder Traversal: Recursively traverse the left subtree, then process the root, then recursively traverse the right subtree.

Postorder Traversal: Recursively traverse the left subtree, then recursively traverse the right subtree, then process the root.

Example: Factorial

Termination Condition: If calculating 1 factorial, return 1.

if (n == 1) {
    return 1;
}

Non-recursive Part: The condition above already handles the base case.

Recursive Logic: n! can be computed as n * (n-1)!.

return n * factorial(n - 1);

Summary of Recursion

Recursion is a powerful technique for solving problems elegantly and efficiently. However, its not a universal solution. Limitations like time, space, or stack overflow may prevent its use.

A problem's suitability for recursion often becomes clearer by expressing it mathematically. Identifying the recurrence relation and base case is a prerequisite for using recursion.

Apply memoization when possible. Recursive algorithms may involve redundant calculations (e.g., Fibonacci numbers). Memoization stores intermediate results in a cache for later reuse, improving time complexity at a slight space cost.

Tail recursion can help mitigate stack overflow. In tail recursion, the recursive call is the final action in the function, eliminating the need to maintain a call stack beyond the current call. This makes tail recursion more space-efficient and easier to understand than non-tail recursion.

Reference Article: Recursion Explained

Queue

Only the front and rear elements of a queue are accessible; traversal is not allowed.