- Introduction and word of the author
- What is recursion?
- From while/for loops to recursion
- Chapter 1: Recursion and arrays
- Array sum
- Largest number in array
- Smalles number in array
- Flatten nested array
- Even numbers
- Multiply numbers in array
- Chapter 2: Recursion and strings
- Recursive string reversal
- Get number from a string
- Shortest word in string
- Nested string
- Chapter 3: Recursion and linked lists
- Appending data to linked list
- Delete node at k index
- Reversing linked list with recursion
- Logging linked list data
Chapter 4: Recursion and binary trees
- Creating a binary tree and appending data to it
- Minimum value in binary tree
- Maximum value in binary tree
- Deep first search
Chapter 5: Recursion and backtracking
Chapter 6: Memoization and Tail recursion
- Tail recursion
- Chapter 7: Inner game of recursion
- Recursive leap of faith
- Final words
Introduction and word of the author
Hello and welcome to the book! In this book, I will teach you how to use recursion and most importantly you will gain an understanding of what recursion is.
Recursion is a hard topic to grasp (I know because it took me a while to understand it).
Recursion is a beautiful concept and it will help you solve many hard problems easily.
I just want you to know that you can do it! You can learn recursion. I will teach you how to to use recursion on arrays, strings, nested objects (trees). I will give you step by step examples, so you can see how recursion works under the hood and effects that have on memory.
Just a disclaimer, in the book the function declarations are used. It is easier for beginners to grasp recursion, instead using arrow functions. Arrows functions are used for callbacks. I hope you enjoy the book!
What is recursion?
A recursive function is a function that it calls itself. Simple as that! Let me give you an example:
That right there is recursion! But wait! If you run the code, it will run infinitely number of times (or until you have memory). (Do not run this code, it will freeze your browser or browser tab, it is just for demonstrating purpose)
We need a way to stop the recursion
We need some condition that when is met it will stop calling the function.
That condition is called a base case
 - This is a base case, the place where a function is stopped and returns an n.
 - Here the n is incremented by one.
Look at this, you can console.log the n, just like in normal loop.
It will log numbers until 10. Simple, right?
From while/for loops to recursion
You saw on the last few pages what recursion is. Let’ s convert some while/for loops to recursion, so you can start using recursion right away instead of normal loops!
Now, let' s start adding multiple arguments!
Here we have a recursive function with two parameters. You can put as many parameters as you want. Parameter k is always the same number. And we increment n by one. Let us see another example:
I hope you understand now recursion on the basic level, and you know how to use it instead of basic loops. Good job! Let us keep moving forward!
Chapter 1: Recursion and arrays
Let us see how we can use recursion with arrays!
First, let us sum the array! Pretty simple, but pay attention!
How come this works? Let me introduce you to new concept called the Stack
A stack is a LIFO ( Last In First Out) data structure.
This means that every recursive function call is put on top of the stack and removed from the stack when the recursive call is done! Let us analyze step by step sumArr function
Step 1 -> 1 + sumArr([2,3,4]);
Step 2 -> 1 + 2 + sumArr([3,4]);
Step 3 -> 1 + 2 + 3 + sumArr();
Step 4 -> 1 + 2 + 3 + 4 + sumArr();
Okay, we got to the end of the stack, what now? The recursion has reached base case. Now the stack unwinds! Remember how I told you that stack is LIFO (Last In First Out). Watch!
- 1 + sumArr([2,3,4])
- 1 + 2 + sumArr([3,4]);
- 1 + 2 + 3 + sumArr()
- 1 + 2 + 3 + 4 + sumArr()
Yea! We got the right summed number. This is how recursion works behind the scene. Very nice, right? I want you to see how we can iterate array with recursion.
We splice array items by one, meaning array length will change the more computer puts functions on the stack.