You need a good understanding of how functions work before learning recursion. I have used Python code for examples in this article because of its simple syntax, but the concept of recursion is the same for every programming language.

What is Recursion?

In most programming languages, a function can call another function. But a function can also call itself. Recursion is the technique where a function calls itself.

Here's an example:

def call_me():
    call_me()

Here, the function calls itself, which is called recursion.

But "calling itself" is just a programmatic definition of recursion. Recursion involves breaking down a problem into smaller pieces to the point that it cannot be further broken down. You solve the small pieces and put them together to solve the overall problem.

Real Life Analogy of Recursion

Lets understand how recursion really works with the help of an example.

Imagine you're in line for a Disney ride, and you don't know how many people are ahead of you.

To find out, you ask the person in front of you.

Trying to find out how many people are in front of you in line

That person also doesn't know, so they ask the person in front of them.

This process continues until the question reaches the person at the very front of the line, who sees that there is no one in front of them and replies that there are zero people ahead.

The replies then start to propagate back through the line. Each person adds one to the number they were told before passing the information back.

When the person at the front replies, "There are 0 people ahead" the next person adds one and replies, "There is 1 person ahead" and so on.

Everyone knows how many people are in front of them in line

By the time the response reaches the person directly in front of you, they add one more and tell you. This way, you can determine your position in the line by just adding 1 to the number the person in front of you gave.

This example illustrates how recursion breaks a problem into smaller subproblems and then combines their solutions to solve the original problem.

Each person in the line represents a smaller instance of the same problem: determining the number of people ahead. By solving these smaller instances and combining their results, the overall problem is resolved. This is exactly how recursion works.

Technical Details of Recursion

The most important things to consider while coding recursion is to find out:

• Recursive Case: Minimum work we can do. In the above example, asking the person in front of you how many people are ahead of them is the least amount of work we can do.

• Base Case: Condition where no work is required. In the above example, the person on the front of the line doesn’t have to ask anything so it is the condition where no work is required.

Simple Example of Recursion

Calculating a factorial is the simplest example of recursion that will really help you understand how it works.

There are many ways to calculate the factorial of a number. But here we will see the recursive way to find it.

Before thinking about how we do it, we need to know what the factorial of a number is.

The factorial of a number is the multiplication of all numbers from 1 up to that number.

For example, the factorial of 5 is 120 – that is 5×4×3×2×1.

We can also represent this mathematically like this:

5×(5−1)!

This means that if we know the value of (5−1)! we can easily get the factorial by just multiplying 5 by it.

Here’s how we find the factorials of 4, 3, 2, 1, and 0:

Factorial of 4 = 4×(4−1)!
Factorial of 3 = 3×(3−1)!
Factorial of 2 = 2×(2−1)!
Factorial of 1 = 1
Factorial of 0 = 1

By looking at this, it is clear that to find the factorial of 5, we must multiply 5 by 4!.

More general example

To find the factorial of n, we need to multiply n with (n−1)!. This is something you need to do recursively.

Now, there must be a stopping condition for recursion. The stopping condition is where we perform no further operation. When n is 1 or n is 0, we can simply stop the recursion as these values have known factorials. We can simply say the factorial of 1 is 1 and the same is true for 0.

So, breaking it down, the minimum amount of work we need to do to find the factorial of n is n×(n−1)!. And we can stop performing operations on it when we find the factorial of 1 or 0.

Let's see how it looks in code:

# calculate factorial of n
def fact(n):

   # no work required
    if n == 1 or n == 0:
        return 1

    # minimum amount of work
    return n * fact(n - 1)

n = 5

# calculate factorial
factorial = fact(n)
print(factorial)

Output:

120

Let's see how it works:

In the first function call, the factorial of 5 is evaluated. Then in the second call, the factorial of 4 is evaluated, and so on until the factorial of 2 is evaluated.

Recursively calculating Factorial of 5

While calling the factorial of 2, we have 2×fact(2−1), which is 2×fact(1).

This hits our base case. So, the recursion stops and 2×fact(1) returns 2×1 to the preceding function call, and the result gets popped up the stack.

Fourth function call returning 2 to preceding function call and getting popped up from the stack

Similarly, here’s how everything else evaluates:

3rd function call returning 6 to the preceding function call and getting popped up from the stack

2nd function call returning 24 to the preceding function call and getting popped up from the stack

1st function call returning 120 to the initial function call and getting popped up from the stack

So the function finally returns the value 120 to the initial function call.

Why Do We Need a Base Case?

In the above example we have used the stopping condition for the code. But what if we don’t add a stopping condition or what if the function we write never meets the stopping condition?

Will the code run forever?

No – even if you don’t terminate, your code won't run forever. Let’s understand why this is the case with the help of an example.

def print_five():
    print(5)

    # call itself
    print_five()

# function call
print_five()

Output:

5
5
5
...

RecursionError: maximum recursion depth exceeded

If you run the above code, you will see that the function doesn’t run forever and ends with a message RecursionError: maximum recursion depth exceeded.

When a function is invoked, it is stored in a call stack. Here's how the function print_five() is stored in the call stack when it is invoked for the first time.

Call stack on the first function call

The function calls itself again and again, and the function is stored in the call stack with each call.

Call stack after n function calls

But the call stack has a limited size and cannot store an unlimited number of functions.

No space on call stack resulting in stack overflow

When the stack is full, it cannot accommodate any more calls, causing a stack overflow error.

Therefore, the base case is essential to prevent such errors and ensure the recursion terminates properly.

Now let's see another example to understand recursion even more.

How to Check if a Word is a Palindrome

Before we dive into the code, you should know what a palindrome is. A palindrome is a word that reads the same forwards and backwards.

For example, racecar reads the same forwards and backwards.

To check if a word is a palindrome, we have to check if the first and last letters are the same. If they are, we then check if the second and second-to-last letters are the same.

Check if first and last characters of racecar are the same

In the context of racecar, the first and last letters are the same, so we check if the second and second-to-last letters are the same. They are, so now we check if the third and third-to-last letters are the same. Now there is only one letter left to check. A single letter is always a palindrome because it reads the same both ways.

How to check if racecar is a palindrome

So, now let's try thinking about it recursively, which involves the minimum amount of work and determining when no work is required.

Minimum amount of work

Check if the first and last letters are the same, and if they are, remove the first and last letters from the word.

No work required

When there is one letter or no letters left at all, we can simply say it is a palindrome.

Now, let's see how the code looks:

# check palindrome
def check_palindrome(text):

    # stopping condition
    # if the size of text is 1 or 0 return true
    if len(text) == 0 or len(text) == 1:
        return True

    # least amount of work
    # check if first and last char are the same
    # if same remove first and last char from string
    if(text[0]==text[-1]):
        return(check_palindrome(text[1:-1]))

    return False

# check if string is palindrome
text = "racecar"
is_palindrome = check_palindrome(text)
print(is_palindrome)

Here's how the above code works:

Check if racecar is a palindrome

Check if racecar is a palindrome

When to Use Recursion

Recursion can appear elegant and simple. But it often requires many steps to solve even simple problems due to the CPU overhead from repeatedly adding methods to the stack. So before using it, make sure you carefully consider whether it's the right solution for your problem.

When code requires multiple loops and looks confusing and messy, recursion can offer a cleaner solution. Its use, however, depends on the specific code and the type of data or data structure involved. For data structures like trees and graphs, recursion can be particularly useful.

Despite its simplicity in appearance, recursion can be hard to understand and may take multiple steps even for simple problems. So again, make sure you think about your particular use case.

Wrapping Up

This is just an introduction to recursion. There are many cases where recursion is used, and you might be confused about how everything works. I will cover more advanced examples on recursion in the next article.

By the way, here are the resources that I found simple and useful while learning recursion:

• freeCodeCamp video on recursion: I have to give a shout-out to freeCodeCamp for their excellent video on recursion, which inspired much of this article.

• Recursion by Programiz Pro: Another good resource is the Recursion course by Programiz. It's a premium course, so it's not free, but it's thoughtfully designed. Plus, you can actually practice directly on their platform, which makes it well worth it.

No matter where you learn from, don't spend too much time searching for the perfect resource. Just grasp the concepts and start practicing—that's the only way you'll truly learn.

In this article, you will learn what linked lists are, how they work, and how to build one.

While the concepts discussed are not specific to any particular programming language, this article will use Java to demonstrate how to create a linked list programmatically.

What is a Linked List?

A linked list is a collection of nodes where each node contains data as well as the memory address of the next node in the list.

Illustration of a linked list with three nodes

Here, you can see that the addresses of the nodes are not necessarily immediately sequential. The first node has an address of 200 and the second node has an address of 801, instead of 201 as you might expect.

Then how are the nodes stored linearly?

Even though the nodes are not in a contiguous memory, the nodes are stored linearly through links. Every node has the address of its succeeding node. That is how each node can access its succeeding node.

Nodes in a Linked List

Nodes are the building block of the linked list. After all, a linked list is a collection of nodes.

Example node

A node in a linked list consists of two parts:

• data which denotes the value of the node.

• next which is a reference to the succeeding node.

Head and Tail in a Linked List

As mentioned earlier, a linked list is a collection of nodes.

Illustration of a linked list showing the head and tail

The first node of the linked list is called the head node. It is the starting point of a linked list.

The last node is called the tail node. As there is no node after the last node, the last node always points to the null.

A null pointer does not point to any memory location.

How to Create a Linked List Programmatically

At this point, you should have basic knowledge of how a linked list works and its structure. Let’s create a linked list with the following steps:

• Create node.

• Connect nodes.

• Append nodes.

• Insert nodes.

• Delete nodes.

How to Create a Node in a Linked List

As you know, a node consists of two parts: the data and the address to the next node.

Illustration of a single node

Here's how you can create a class called Node:

class Node {
    int data;
    Node next;

    Node(int data) {
        this.data = data;
        this.next = null;
    }
}

The Node class represents a node in a linked list, with two instance variables: data (holds the data stored in the node), and next (holds a reference to the next node in the list).

The constructor takes an int argument data to initialize the data variable and sets the next variable to null by default.

Now, you can simply create nodes and add data to them by creating new instances of the Node class:

// create nodes
Node node1 = new Node(11);
Node node2 = new Node(18);
Node node3 = new Node(24);

In the code above, we created three nodes:

Showing the three nodes we created with the above code

How to Link the Nodes in a Linked List

After creating the nodes, you must connect them to form a linked list.

To do this you first need to create a linked list with a head node.

class LinkedList {

    Node head;

        LinkedList() {
        this.head = null;
    }

}

Initially the head node is set to null because there are no nodes in the linked list yet.

Now to connect the nodes together in a Linked List, you can start by setting the head node to the first node in the list, in this case node1.

head = node1;

Then make the next of node1 point to node2, and the next of node2 point to node3. That is:

node1.next = node2;
node2.next = node3;

Illustration showing the linking of nodes

You have successfully created a linked list and connected the nodes.

How to Append a Node to Linked List

Appending a node means adding a node to the end of a linked list. There are two cases to consider when appending a node:

• Appending to an empty linked list.

• Appending to a non-empty linked list.

How to Append a Node to an Empty Linked List

If there are no nodes in a linked list, it is an empty linked list. To append a node to an empty linked list, you must first make sure the linked list is empty. You can do this by checking if the head node is null.

If the head node is null then you can simply set head to the new node:

if (head == null) {
    head = newNode;
}

Head node is null

How to Append a Node to Non-Empty Linked List

If there are one or more nodes in a linked list, it is a non-empty linked list.

Illustration of a non-empty linked list

To append a node to a non-empty linked list, make the last node link to the new node.

Unlike arrays, we cannot access any elements in a linked list directly. We must traverse from the head node to the last node.

To do that, create a temporary pointer (you can call the pointer current) that points to the head node.

Illustration showing temporary pointer (current) pointing to head node

Next, make current point to its next node, till the next of the current node points to null.

Illustration showing temporary pointer (current) pointing its next node

Illustration showing temporary pointer (current) pointing its next node

When the next node of current is null, you can then make the next of the current node point to the new node. That is:

Illustration showing temporary pointer (current) pointing to new node

while (current.next != null) {
    current = current.next;
}
current.next = newNode;

How to Insert a Node in a Linked List

Inserting a node means adding a node to a given index. There are two cases to consider when inserting a node:

• Inserting a node at the first index.

• Inserting a node at a given index.

How to Insert a node at the First Index

To insert a node at the first index:

• make next of the new node point to the head node

• set the head to the new node

Illustration showing new node pointing to head node

Illustration showing head node pointing to the new node

if (index == 0) {
    newNode.next = head;
    head = newNode;
}

How to Insert a Node at Any Position

Linked List with index

Let’s suppose you want to add a node at index 2 in the linked list above.

To insert a node at index 2, you must traverse the node that comes before index 2.

Illustration showing temporary pointer (current) pointing to head node

Illustration showing temporary pointer (current) pointing its next node

Next, create a new node and make the next of the new node point to the next of the current node.

Illustration showing new node pointing next node of current

Make the next of current point to the new node.

Illustration showing current pointing new node

Here's the code to do all this:

for (int i = 0; i < index - 1 && current != null; i++) {
    current = current.next;
}
if (current != null) {
    newNode.next = current.next;
    current.next = newNode;
}

How to Delete a Node in a Linked List

There are two ways to delete nodes in a linked list:

• Deleting the head node.

• Deleting a node at a given position.

How to Delete the Head Node

Deleting the head node of a linked list is simple. You can store the data of the head node in a temporary variable if it needs to be accessed later. Then set the head pointer to point to the next node after the head node.

Illustration showing temporary pointer (current) pointing to head node

Illustration showing temporary pointer (current) pointing its next node

if (index == 0) {
    deletedValue = head.data;
    head = head.next;
}

How to Delete a Node at a Given Position

Suppose you want to delete the node at index 2 in the diagram below:

Linked List with index

You can delete the node at index 2 by making the node at index 1 point to the node at index 3.

To delete a node you must access the node you want to delete and the node before it. Take two temporary pointers (you can call the pointers previous and current). Let previous point to null and current point to the head node.

Illustration showing temporary pointer (current) pointing to head node

Now, move current one step forward and move previous to current till you reach index 2.

Illustration showing temporary pointer (previous) pointing to head node

Illustration showing temporary pointer pointing to its succeeding nodes

Make the next of previous point to the next of the current node.

Illustration showing previous pointing to node next to current

Then store the data of current in a variable for future use.

After removing the link to the node at index 2, it is no longer accessible through any reference in the linked list.

It's important to note that when removing a node from a linked list, you don't need to explicitly delete the node itself at the given index. This is because the removed node will be automatically handled by the garbage collector when it is no longer reachable through any references.

However, in languages like C or C++, which do not have automatic garbage collection, you need to manually delete the node when it is no longer needed to avoid memory leaks and wasted memory resources.

for (int i = 0; i < index && current != null; i++) {
    previous = current;
    current = current.next;
}

if (current != null) {
    deletedValue = current.data;
    previous.next = current.next;
}

Complete Linked List Code

The code below shows a complete linked list. You can create, append, insert, delete, and display the nodes in the linked list:

class Node {

    int data;
    Node next;

    Node(int data) {
        this.data = data;
        this.next = null;
    }
}

class LinkedList {

    Node head;

    LinkedList() {
        this.head = null;
    }

    public void createLinkedList() {

        Node node1 = new Node(11);
        this.head = node1;

        Node node2 = new Node(18);
        node1.next = node2;

        Node node3 = new Node(24);
        node2.next = node3;
    }

    public void append(Node newNode) {

        Node current = this.head;

        if (current == null) {
            this.head = newNode;
        } else {
            while (current.next != null) {
                current = current.next;
            }
            current.next = newNode;
        }

    }

    public void insert(Node newNode, int index) {

        Node current = this.head;
        if (index == 0) {
            newNode.next = current;
            this.head = newNode;
        } else {

            for (int i = 0; i < index - 1 && current != null; i++) {
                current = current.next;
            }
            if (current != null) {
                newNode.next = current.next;
                current.next = newNode;
            }

        }

    }

    public int delete(int index) {

        Node current = this.head;
        Node previous = null;
        int deletedValue = -1;

        if (index == 0) {
            deletedValue = this.head.data;
            this.head = this.head.next;
            return deletedValue;
        }

        else {
            for (int i = 0; i < index && current != null; i++) {
                previous = current;
                current = current.next;

            }
            if (current != null) {

                deletedValue = current.data;
                previous.next = current.next;
            }
            return deletedValue;
        }
    }

    public void displayLinkedList() {

        Node current = this.head;
        while (current != null) {
            System.out.println(current.data);
            current = current.next;

        }
    }

}

class Main {
    public static void main(String[] args) {
        LinkedList l1 = new LinkedList();
        Node newNode1 = new Node(22);
        Node newNode2 = new Node(43);
        Node newNode3 = new Node(5);
        l1.createLinkedList();

        l1.append(newNode1);
        l1.insert(newNode2, 0);
        l1.insert(newNode3, 2);
        l1.delete(2);
        l1.displayLinkedList();
    }
}

Wrapping Up

The linked list data structure can be used in various applications, such as web browsers and music players.

For example, in a web browser, the browser history can be stored as a linked list. Each page visited can be represented by a node, with the link pointing to the next page visited. This allows for easy navigation through the history, by simply traversing the linked list.

Similarly, in a music player, the playlist can be represented as a linked list. Each song can be represented by a node, with the link pointing to the next song in the playlist. This allows for easy navigation through the playlist, by simply traversing the linked list.

It is not very likely that you will create a linked list for your applications, as almost every programming language has a built-in linked list.

However, creating one and understanding its implementation can deepen your knowledge of the data structure. This knowledge can help you determine when to use a linked list over other data structures in real-life applications.