How I Learned The Intuition Behind Recursion

jeromecaisip — Tue, 02 Feb 2021 05:39:44 +0000

When I was studying data structures and algorithms, I did some exercise implementing BST(binary search tree) and its operations.

I was able to implement insert and search using iteration because it's more intuitive for me compared to using recursion, until I have to work on the delete operation, specifically on the case where the node I need to delete has 2 children. For context, in order to this, I had to identify the left most node of the right subtree and use its value to replace the value of the node I intend delete.

Using iteration looks easy for BST with a height of 2 or 3 even. However, as I was trying to test it on cases wherein the height of tree is 4 or greater, the code got complicated. So I reset my thoughts, then looked at the problem in a different perspective, then it hit me! A node of a BST is a BST itself! And this applies to linked-lists and array as well, a node of a linked-list is a linked-list, an index of an array is an array.

Then I suddenly remember what Prof.Skiena said, from a reader of his book, on one of his lectures about building a mental model for recursion.

If you take a bite out of a salad, you get a smaller salad. But if you took a bite from a hamburger, you don't get a smaller hamburger.

Here's the output of my work:

DEV Community: jeromecaisip

How I Learned The Intuition Behind Recursion