The ultimate guide to recursion interviews with strategies developed by FAANG engineers. Practice with real-world interview questions, detailed explanations, and visualizations to prep faster.

If you’ve got an interview coming up and want to brush up on your knowledge, or if you’ve ever struggled with solving coding problems using recursion, you'll find this course helpful.
 
You’ll start with the basics of what recursion is and why it’s important before diving into what it looks like in practice. You’ll see how recursion can help you solve a variety of different math, string, and data structure problems by using interactive code playgrounds that you can execute directly in your browser. You’ll have access to detailed explanations and visualizations for each problem to help you along the way.  
 
By the time you’re done, you’ll be able to use what you’ve learned to solve complex real-world problems and even advance more easily through your interviews at top tech companies.

Recursion for Coding Interviews in Java

# Sum n numbers

When given a linked list, sum the values of all the nodes and then return the sum.

The following illustration explains this concept:

# Implementing the code

The following code calculates the sum of the node values in the linked list using recursion.

Experiment with the code by changing the elements of the list to see how it works.


class LinkedList {

    // Linked List Node
    static class Node {
      int value;
      Node next;
    };

    static int sumList(Node head) {

      // Base case
      if (head == null) {
        return 0;
      }

      // Recursive case
      else {
        return (head.value + (sumList(head.next)));
      }
    } 

    static Node insertAtHead(Node temp_head, int new_value) {
      Node new_Node = new Node();
      new_Node.value = new_value;
      new_Node.next = (temp_head);
      (temp_head) = new_Node;

      return temp_head;
    }

    public static void main( String args[] ) {
        // Empty Linked List
        Node head = null;

        // Linked List = 3->1->5->8->2
        head = insertAtHead(head, 2);        
        head = insertAtHead(head, 8);        
        head = insertAtHead(head, 5);        
        head = insertAtHead(head, 1);        
        head = insertAtHead(head, 3);

        System.out.println("Linked List: ");
        for (Node i = head; i != null; i = i.next) {
          System.out.print(i.value + " ");
        } 

        int sum = sumList(head);

        System.out.println(" ");
        System.out.println("Sum: " + sum);
    }
}

# Understanding the code

The code given above can be broken down into **two parts**: the  **recursive method** and the **main** where the method is called.

## Driver method
The driver code is found from **line 32 to line 50**.

* In the driver code, between **lines 36 and line 40**, a linked list is created by inserting five nodes using the `insertAtHead` method. 

* The `sumList` method is called on **line 47**, which takes only 1 argument: the `head`, which points to the head of the list.

* The method `sumList` returns the sum of numbers in a list when it is called. 


## Recursive method
Each recursive method has two parts: **base case**  and the **recursive case**.

### Base case
The base case is defined on **line 12**.

If the list has been fully traversed, meaning `head` equals null,the method returns the sum of numbers in a list. It also covers the case when the list is empty, i.e, head equals null then the method should simply terminate.

### Recursive case
The recursive case is defined on **line 18**.
* The method takes only 1 argument the `head` which is a  pointer that points to the first node of the list. The `head` of the list gets updated with each call to the method.

* Initially, the `head` points to the start node.

* With every successive recursive call, the `head` points to the next node while summing up the value of the `head` node.

* When the `head` points to null, meaning, it reaches the end of the list, the base case is reached.

* The sum of numbers in a linked list is returned.

This lesson will teach you how to calculate the sum of numbers in a linked list using recursion.

Fundamentals of Recursion

Iteration to Recursion

Recursion with Numbers

Recursion with Strings

Recursion with Arrays

Recursion with Data Structures

Sum Numbers in a Linked List

Sum n numbers