Understanding Recursion in Programming - freeCodeCamp

Notes from this tutorial

Photo by Lloyd Henneman on Unsplash

This post contains the notes I took from this freeCodeCamp video on youtube. I have included all the definitions (theoretical part) and problems solved in JavasScript.

Recursion: A process in which a bigger/complex problem is broken down into smaller subproblems and we solve those subproblems to solve the bigger problem.

Pros:

1. Bridges the gap between elegance and complexity.
2. Reduces the need for complex loops and auxiliary data structures.
3. It can reduce time complexity easily with memoization.
4. Works really well with recursive data structures like trees and graphs.

Cons:

1. Slowness due to CPU overhead.
2. Can lead to out of memory errors/StackOverflow exceptions.
3. Can be unnecessarily complex if poorly constructed.

Callstack:

A call stack is a mechanism for an interpreter (like the JavaScript interpreter in a web browser) to keep track of its place in a script that calls multiple functions — what function is currently being run and what functions are called from within that function, etc. (read more here…)

Error in the call stack (StackOverflow): It’s an exception that happens when we exceed the pre-allocated buffer of memory that our program has.

Problems:

1. Reverse a string:

• Base case: If the string is empty then return.
• Recursive Function: Else call the function again on the substring starting from index 1 and add the character at the 0th index at the end.

2. Palindrome:

• Base Case: If the length of the input string is 0 or 1 then return true.
• Recursive Function: check if the char at 0th index and last index (str.length - 1) are equal. Return the function again on the substring from the 1st index to the second last index of the string.
• Return false (another base case)

3. Decimal to Binary:

• Create a variable (result) to store the binary number.
• Base Case: If the decimal is 0 then the return result.
• Operation: Add (decimal % 2) to the previous result value. (result += decimal % 2)
• Recursive Call: Call the function again with the quotient value i.e. decimal/2.

Note: Another way of converting decimal to binary recursively.

4. Sum of Natural Numbers:

• Base Case: If the number is zero then return the result.
• Operation and Recursive Call: Add the current number to the recursive call of the function with num - 1.

5. Binary Search:

• Base Case: If the left index (smaller) is greater than the right index (bigger) return -1.
• Operation: Find the mid-index and check if the element at the mid-index is equal to the target then return true.
• Recursive Call:

1. If the element is greater than the mid element then call the function with the right index being mid-1.
2. Otherwise, call the function with the left index being mid+1.

6. Fibonacci Series:

• Base Case: If the number is 0 or 1 then return the number.
• Operation + Recursive Call: Return the sum of the function call with (num-1) and (num-2)

Note: This is not an optimized way of calculating the nth Fibonacci number.

7. Merge Sort:

• Base Case: Return the array if the length(array) ≤ 1.
• Operation: Calculate the index of the mid element i.e. length(array)/2.
• Recursive Call: Call the function again from the 0th to mid-index (left part) and from mid-index to the index of the last element (right part).
• Return the helper function that will merge the left and right parts.

8. Linked List Reversal:

• Base case: If the head and head.next are null then return head.
• Recursive Call: Call the head.next recursively and store it in a variable (p).
• Operation:

1. Set head.next.next to head
2. Set head.next to null
3. Return the variable (p)

9. Merge Two Sorted Linked Lists: given two heads h1 and h2 in arguments

• Base Case: If h1 and h2 are null, return undefined or if one of them is null, return the other one.
• Recursive call + Operation:

1. If (h1.value < h2.value) recursively call the function and set h1.next to be function(h1.next, h2) and return h1.
2. Else recursively call the function and set h2.next to be function(h1, h2.next) and return h2.

10. Insert a Value in a Binary Search Tree:

• Base Case: If the root of the bst is null then set the root to be the new value.
• Recursive Call + Operation:

1. If (value > root.value) then recursively call the function on root.right
2. Else call the function on root.left

11. Print all leaf nodes:

• Base Case: If the left and the right child of a root are null then its the leaf node.
• Recursive Call:

1. If root.left is not null call function(root.left)
2. If root.right is not null call function(root.right)

Memoization: It helps in increasing the performance of the functions by storing the output of computationally expensive function executions and returning the cached result when the function is called again with the same input.

Tail Call Recursion: A recursive function is tail-recursive when a recursive call is the last thing executed by the function.

All the sources:

Memoization

Tail Recursion - GeeksforGeeks

Call stack - MDN Web Docs Glossary: Definitions of Web-related terms | MDN