# Linked List Challenge Solution 1

The task is to:

``````Create a function that prints the nodes of a linked list in reverse order. For example:
1 -> 2 -> 3 -> nil

// should print out the following:
3
2
1
``````

The solution in the book is the following:

``````private func printInReverse<T>(_ node: Node<T>?) {
guard let node = node else { return }
printInReverse(node.next)
print(node.value)
}

func printInReverse<T>(_ list: LinkedList<T>) {
}

``````

Evidently, the challenge is solved using “recursion” here. I had to lookup what recursion meant as it wasn’t even mentioned earlier in the book. I would expect a solution to use methods mentioned in the book at least. The explanation was also very vague for a solution that uses a method not discussed in the book. I strongly suggest a short section on recursion be added to the book.

Anyway, after several hours I just don’t understand how this solution works. I understand how to accomplish this iteratively, but recursion is not clicking for me. I understand a few points about the solution such as, we only move to the next node and print once we get to the end of the list but that’s it.

In other words, I understand how we print “3” (the first reversed node) but not the others. How are we able to go backwards (i.g. 2 → 1) if a linked list is unidirectional???

I also don’t understand the role of the below function:

``````func printInReverse<T>(_ list: LinkedList<T>) {
}
``````

Can someone please explain how this works?

@mjhios Recursion happens when a certain function calls itself. All recursive function calls are stored on the stack which works in LIFO mode. LIFO stands for last in first out and is a fancy way of saying that you can only add and remove items at the top of the stack. You can think of the stack as a pile of books or dishes. If you attempt to either add or remove anything in the middle or at the bottom of the stack everything else collapses. So it makes sense to only be able to work with the top item of the stack in this case no matter what.

`printInReverse(_ list:)` is a generic overload of `printInReverse(_ node:)`. The list version of the function calls its overloaded node version using the head of the list as its argument. `printInReverse(list.head)` doesn’t print anything to the console if `list.head` is `nil` since it’s an empty list in this case and calls `printInReverse(list.head.next)` otherwise. Each `printInReverse(_ node:)` function call calls `printInReverse(_ node:)` for the next node in the list if the current node isn’t `nil`. The compiler pushes all recursive function calls to the stack in the order they happen using the LIFO rule. This is how the stack trace looks like for a list with three nodes:

```printInReverse(list.head.next.next)
```

Once you reach the end of the list and the current node is `nil`, the compiler automatically unwinds the stack for you under the hood. Each recursive function call gets popped from the stack using the LIFO principle. The compiler first pops `printInReverse(list.head.next.next)` from the stack which prints `list.head.next.next.value` to the console which is 3 in this case. The compiler then pops `printInReverse(list.head.next)` from the stack which prints `list.head.next.value` to the console which is 2 in this case. The compiler finally pops `printInReverse(list.head)` from the stack which prints `list.head.value` to the console which is 1 in this case. The stack is empty so you are done.

It’s very important that the chain of recursive function calls stops at some point so the compiler can unwind the recursive stack safely. Otherwise you get a stack overflow error. You can think of this as an endless loop with no exit condition.

You can read even more about recursion vs iteration over here:

Please let me know if you have any more questions or other issues about the whole thing when you get a chance. Thank you!

@shogunkaramazov Thanks for the reply! I didn’t know the compiler was using a Stack (LIFO) under the hood. Nice! Just a few points I still don’t understand.

You mentioned:

`printInReverse(_ list:)` is an overload of `printInReverse(_ node:)` . The list version of the function calls its overloaded node version using the head of the list as its argument. `printInReverse(list.head)` doesn’t print anything to the console if `list.head` is `nil` since it’s an empty list in this case and calls `printInReverse(list.head.next)` otherwise.

Above you mentioned that `printInReverse(list.head)` doesn’t print anything if `list.head` is `nil` (end of list). Instead it calls `printInReverse(list.head.next)` but I thought it would call `printInReverse(list.head.next.next)` which would be `list.head.next.next.value` or 3 in this case?

Also, I’m still not sure I understand the role of the below function:

`````` func printInReverse<T>(_ list: LinkedList<T>) {
}
``````

If I understand correctly, all it does is get a linked list, call `printInReverse<T>(_ node: Node<T>?)`, and push `list.head` (1, 2, 3) to the call stack. Once the list is `nil` `printInReverse<T>(_ node: Node<T>?)` pops (and prints) the node values 3, 2, 1 right? Or am I still not understanding how it interacts with the helper function?

Thanks, I really appreciate it!

@mjhios This is what happens step by step with a list that has three nodes:

1. `printInReverse(list)` calls `printInReverse(list.head)`.

2. The stack pushes `printInReverse(list.head)` which checks that `list.head` isn’t `nil` and calls `printInReverse(list.head.next)`.

3. The stack pushes `printInReverse(list.head.next)` which checks that `list.head.next` isn’t `nil` and calls `printInReverse(list.head.next.next)`.

4. The stack pushes `printInReverse(list.head.next.next)` which checks that `list.head.next.next` isn’t `nil` and calls `printInReverse(list.head.next.next.next)`.

5. `printInReverse(list.head.next.next.next)` checks that `list.head.next.next.next` is `nil` and returns.

6. The stack pops `printInReverse(list.head.next.next)` which prints `list.head.next.next.value` that is 3 in this case and returns.

7. The stack pops `printInReverse(list.head.next)` which prints `list.head.next.value` that is 2 in this case and returns.

8. The stack pops `printInReverse(list.head)` which prints `list.head.value` that is 1 in this case and returns.

9. `printInReverse(list)` returns.

Please let me know if you have any more questions or other issues about the whole thing when you get a chance. Thank you!