How❓Do You 🧐 Teach Recursion 🪗 to an 8 Year Old 👧🏻 | Make Believe 🎅🏻 and Wishful Thinking 🦸🏻♀️ | Series 01 | Recursion 🤹🏻 | Part II

Believe it or not the real super-power of recursion comes from a kind of make believe or wishful thinking where you kind of assume you've already solved the problem (without having solved it) and the solution somehow magically falls out of the assumed solution. Sounds circular? Isn't recursion itself circular? It's really like make believe or wishful thinking done carefully. Making it ideal to teach to kids. Think it's too good to be true? Let's take a look at what I mean.

Let's take the classic problem of reversing a linked list.

LC Easy 206. Reverse Linked List

Easy

Given the head of a singly linked list, reverse the list, and return the reversed list.

Example 1:

Input: head = [1,2,3,4,5]

Output: [5,4,3,2,1]

Example 2:

Input: head = [1,2]

Output: [2,1]

Example 3:

Input: head = []

Output: []

Firstly recursion is about breaking the problem into smaller parts. What is easiest decomposition of this problem into smaller units? Take the first node of the list and the rest of the list (the tail) to be the smaller subproblem (1 smaller than the original problem). Now let's assume that magically the tail is already reversed. We made a wish and someone just gave it to us. If so where would the first element fit? At the end of the remaining reversed list right? Okay let's visualize this.

So what the hell is going on here? Even your child would ask you where do we pay the piper? And the answer actually lies in one of the oldest and most foundational elements of Mathematics and Logic. It's called Induction. When you learn Induction for the first time it also feels weird and kind of impossible and takes a little getting used to. The Principle of Mathematical Induction (roughly) states that if we have proved a property P(n) for n = 1 and assume it's true for all n up to k - 1 and prove that it's true for n = k then you have proved the property P(n) holds true for all natural numbers.

The two most important aspects of Induction and recursion are the

1. Proving / Evaluating for n = 1 (step also called the base case)
2. Proving / Evaluating the case n = k assuming / using the smaller cases n = k - 1 and smaller subproblems

Let's see what this looks like in code. Let's first think of the base case. When you're given an empty list (head is None) or a list with a single node (head . next is None). In each of those cases you just return the head. There's nothing to reverse really.

Now for the recursive non-base case (head . next is not None)

So we don't have the end of the reversed list to be able to attach the head at the end. Now we could traverse all the way to the end and attach it but that would make every single attach O(n) and the whole solution becomes O(n^2). That's not acceptable (at least intuitively it feels like we should be able to reverse a list of n nodes in O(n) steps. Right?)

Again the answer is simpler than what one might imagine. If you don't have the end (let's call this toe) then make the wish for both the head and the toe of the reversed list and you shall have it from the magic recursion fairy! Basically return both head and toe from the function.

Let's see what this looks like in code

So I guess we are done right? Let's run this and see what happens :)

The reason to show this wrong code and it's execution result / failure is to point out the classic rookie (beginner's) mistake. And that is not thinking through the pointers correctly. So let's see what exactly is going on here making sure we don't leave out any pointers.

So finally this is what the solution looks like in code. Notice we usually don't want to expose the details of the recursion to a caller so we kind of hide it inside a non-recursive call. Also in this case what is required is just one pointer in the end pointing to the head of the reversed list.

And here's how it performs. Not too bad huh!

Now that we have this way of thinking and reasoning under our belt we can quickly solve many other linked list reversing problems from Leetcode.

Let's try to generalize what we've got here a little bit. We just reversed an entire linked list. How about reversing just the first k nodes? How would we do that?

Now that we have this infinitely utilitarian recursion fairy / genie all we need to do is figure out what to wish for. That seems simple enough right?

First lets severe the head from the tail of the linked list. And it's time to make a wish. Let's visualize what would the final reversed list look like.

Since the recursion fairy is kind of omnipotent let's just ask for the reversal of first k elements and see how that goes remembering to ask for both the head and toe of the k - 1 nodes reversed list following the head that we severed.

But before we do the visualization again let's think about what we'll get back. We'll get back the head of the reversed list pointing to node k. We'll also get a toe that points to node 2. And then we kind of have the dangling list with nodes k + 1 to n.

So we realize it's not that hard after all. Instead of resolving the circularity by pointing the next pointer of node 1 to None we can just point it to the k + 1 th node instead. But wouldn't the next pointer of node k being returned be lost in the process? The answer is no. And to see how to resolve this we need to look at the full picture again.

After we get the head and toe back in the reverse list problem we point it to the current node. But what information does the toe have? We have underestimated the fairy quite a bit here. The fairy solves the problem correctly as required. And we need to strengthen our faith. So when the toe is returned it is pointing correctly to the k + 1 th node. And before pointing the next of toe to node 1 (our current node) we have to extract this information that that the toe has and make good use of it.

How do we capture all the base cases? To see this it's important to understand in what ways is the problem getting smaller in subsequent recursive calls and recognize and handle the edge cases so that

1. You don't fall off (program explodes or returns inconsistent / wrong result)
2. What we return from our base cases they build up to the final solution and so it's extremely important to get these right with each cliff.

The meaning of cliff and what's being said will become clear with the help of a picture.

Let's see finally what this looks like in code. But before that we still need to resolve a few things by making some choices for the base cases. What if k is greater than the length of the list? We can go one of two ways:

1. We don't reverse anything and return the list as is (you'll see this will come handy later).
2. We reverse the whole list (also makes sense if you think about it).

But the cool thing is both these choices will enable us to solve different problems later on. So let's code each one of them and have them in our arsenal for later.

Base cases:

1. k > length ( list ): a) Reverse nothing: return head, toe (of the list) . b) Reverse whole list.
2. k = 1: Do nothing: return head, head
3. Empty List ( head = None): return head, head
4. Single Node List (head . next = None): return head, head
5. k = 0: An otherwise degenerate base case which is prevented by handling the k = 1 base case above. But it becomes clear what to do with it when we look at k = length list and we have reached the end. The most intuitive handling of this is to reverse the whole list.

Recursion | Reverse (the first) k nodes in a Linked List | Identifying and Handling Base Cases

Let's take a look at the code now

You can try playing around with different choices for some of the base cases and see how that changes the behavior of the function. For example if you don't guard for the k = 1 and k = 0 then in all the cases k will keep going down till you hit the list / node cliff of being a singleton or None. And you'll find that the whole list gets reversed in both those cases. Which could be a valid behavior depending on the problem domain you're solving for.

Before we move on to other problems let's do a quick check on the performance and are there things we can do to improve the constants. A few things immediately jump out. When we do n . len we traverse the whole list. Also every time we are not really reversing the list and returning the head and toe as it is returning toe requires one full traversal for no good reason. Can we improve on these scenarios? Sure. Let's see how.

For all intents and purposes the k > n . len case translates to eventually going all the way to the edge of the list and falling off. head = None. And as long as we handle that appropriately to give the result we want for k > n . len we should be good. We shouldn't have to check the length at all. While traversing if we fall of the list that automatically means that k > n . len. That's one traversal saved.

Let's now look at the cases we return n . toe without doing any reversal. Other than the k > len case the only place it happens is when k = 0. In this case we don't reverse the list but because our reverse k recursive function requires returning both the head and the toe we are having to do this unnecessary traversal for no good reason. So let's check that case outside of the recursive function and directly return the head from inside the non-recursive parent reverse k function.

The code below does everything in one traversal instead of two:

I will keep updating this and other articles with more related problems that I solve. So keep an eye out for the latest updates :)

A few of the other problems I plan to solve in this articles future updates are:

2. LC Medium 92 Reverse Linked List II

Medium

Given the head of a singly linked list and two integers left and right where left <= right, reverse the nodes of the list from position left to position right, and return the reversed list.

Example 1:

Input: head = [1,2,3,4,5], left = 2, right = 4

Output: [1,4,3,2,5]

Example 2:

Input: head = [5], left = 1, right = 1

Output: [5]

Follow up: Could you do it in one pass?

All we have to do for solving this problem is:

1. If left == 1 then do a k = (right - left + 1) reverse on the given node
2. If left > 1: reach the left - 1 node
3. Do a k = (right - left + 1) reverse on the left node
4. Set the next of left - 1 node to the reversed output
5. Return the original node
6. And notice we do do it in one pass

3. LC Hard 25 Reverse Nodes in k-Group

Hard

Given the head of a linked list, reverse the nodes of the list k at a time, and return the modified list. k is a positive integer and is less than or equal to the length of the linked list.

If the number of nodes is not a multiple of k then left-out nodes, in the end, should remain as it is. You may not alter the values in the list's nodes, only nodes themselves may be changed.

Example 1:

Input: head = [1,2,3,4,5], k = 2

Output: [2,1,4,3,5]

Example 2:

Input: head = [1,2,3,4,5], k = 3

Output: [3,2,1,4,5]

Follow-up: Can you solve the problem in O(1) extra memory space?

Since we have already solved the reversing k nodes problem the solution to this is as simple as:

1. Firstly if k > len (list): you don't reverse anything. We slightly change the base cases for this
2. k-reverse the list then recursively k-reverse the remaining list

But there's one problem with the above solution though. It checks the length of the list in every call and that's not very efficient. We are having to do that because our reverse k nodes solution reverses the whole list if k > length of the list. And that's the problem because of which we are having to check the length beforehand. So our solution becomes O(n^2 / k) instead of O(n).

What if instead of returning just the head and toe we also return the remaining k value? This would give us an indication of at what value of k did the recursion terminate. If it terminates with a residual value of k = 0 or 1 it's all good. But if it terminates with k >= 2 that means k was greater than the length list and we might be able to do something just for that case.

All that we would need to do in that case is to re-reverse the list before returning it so that it's intact. Which means in the case k > length of the list we do two reversals without a priori checking if k > length of the list which is great. Now our solution should be back to being O(n) overall. This is what it looks like in code and you can see the performance of this function below.

4. LC Medium 24 Swapping Nodes in Pairs

Medium

Given a linked list, swap every two adjacent nodes and return its head.

You must solve the problem without modifying the values in the list's nodes (i.e., only nodes themselves may be changed.)

Example 1:

Input: head = [1,2,3,4]

Output: [2,1,4,3]

Example 2:

Input: head = []

Output: []

Example 3:

Input: head = [1]

Output: [1]

This is just the solution of the previous problem Swap in k-Groups for k = 2. And so the solution is

But of course in an interview or just in general if all you needed was to develop a solution for swap nodes in pairs and not the general solution you can simply do the following:

1. Swap first pair
2. Recursively swap pairs in the remaining list

They both perform the same because in the k-Group solution we stopped calculating length and do everything in one traversal. Otherwise they won't perform the same. The shorter the k the work the performance would be and for 2 it would be the worst as O(n^2 / k) increases inversely with decreasing k.

3. LC Medium 1721 Swapping Nodes in a Linked List

Medium

You are given the head of a linked list, and an integer k.

Return the head of the linked list after swapping the values of the kth node from the beginning and the kth node from the end (the list is 1-indexed).

Example 1:

Input: head = [1,2,3,4,5], k = 2

Output: [1,4,3,2,5]

Example 2:

Input: head = [7,9,6,6,7,8,3,0,9,5], k = 5

Output: [7,9,6,6,8,7,3,0,9,5]

Solution:

1. Find the length l of the list
2. Get the kth node from the front
3. Get the kth node from the back (l - k + 1)th node
4. Swap the values and return the original head

This brings us to the end of Recursion with Linked List. We have tackled much harder problems than just reversing a linked list. And the moral of the story is to meticulously track the pointers in a linked list. As long as you do that and follow the steps of recursion the way it was illustrated you should be golden. If you do have any problems you need help with feel free to comment or message me and I'll be happy to help you out.