Wassim bd

Data structures and algorithms in C++ was probably the course that pushed me the hardest this year. A lot of it clicked eventually, but one topic in particular — linked lists combined with recursion — took me way longer to understand than I expected. Here's what finally made it make sense.

Why linked lists felt harder than arrays

Coming from arrays, linked lists felt unnecessarily complicated at first. With an array, everything is sitting right next to everything else in memory, and you just grab an element by index. A linked list is different: each element (a "node") holds a value and a pointer to the next node. To get to the 5th element, you can't just jump there — you have to walk through the first four nodes to reach it.

struct Node {
    int value;
    Node* next;
};

Enter fullscreen mode Exit fullscreen mode

At first this felt like a downgrade from arrays. Why would I want something slower to access? It took a while to appreciate that linked lists trade fast access for cheap insertion/removal — you don't need to shift a bunch of elements around like you would in an array.

Where recursion comes in

Recursive functions work naturally with linked lists because a linked list is, structurally, a recursive definition: a list is either empty, or it's a node followed by another (smaller) list. That's basically the definition of recursion already baked into the data structure.

Here's a simple example — counting the nodes in a list:

int countNodes(Node* head) {
    if (head == nullptr) {
        return 0; // base case: empty list
    }
    return 1 + countNodes(head->next); // one node + the rest of the list
}

Enter fullscreen mode Exit fullscreen mode

The part that confused me: the call stack

I could write recursive functions like the one above without fully getting why they worked. What clicked for me was visualizing the call stack. Every recursive call to countNodes doesn't run and finish immediately — it pauses, waits for countNodes(head->next) to return a value, and only then adds 1 to it.

So if you have a list A -> B -> C -> nullptr, the calls stack up like this:

countNodes(A) waits on countNodes(B)
  countNodes(B) waits on countNodes(C)
    countNodes(C) waits on countNodes(nullptr)
      countNodes(nullptr) returns 0
    countNodes(C) returns 1 + 0 = 1
  countNodes(B) returns 1 + 1 = 2
countNodes(A) returns 1 + 2 = 3

Enter fullscreen mode Exit fullscreen mode

Once I actually traced through it call by call like that, instead of just trusting that the code "worked," recursion stopped feeling like magic.

Why the base case matters so much

I also learned the hard way (with a stack overflow crash) what happens if you forget the base case, or write it wrong. Without if (head == nullptr) return 0;, the function keeps calling itself forever since there's nothing to stop it. Every recursive function needs a condition that eventually stops the calls — otherwise you're just building an infinitely tall stack until the program crashes.

My takeaway

Linked lists and recursion reinforced each other for me: understanding recursion made linked list operations (counting, searching, reversing) way easier to write, and working through linked lists by hand made recursion finally feel concrete instead of abstract. If recursion still feels like a black box, I'd suggest picking a small linked list problem and literally tracing the call stack on paper, call by call — that's what did it for me.

Final-year software engineering student, writing about what I'm learning in my courses.