Unwinding a never ending recursion ?

It is a very old saying that, all the answers that you seek, lie within you. To seek it, you have to ask your deep inner self, over and over till you reach that central point, from where you unwind all your answers and achieve wisdom. The answers that we are looking for are seldom too far, rather they are too near to us than we can never imagine. In my life, at several phases, I have been astonished by this fact. As I am a Software Engineer by profession, I often try to fuse the philosophy of life with that of code.

In the software domain, when you are looking for answers (It is usually called solutions) and when we are dealing with the code around it, it’s the algorithms that take us to the solutions/answers. A small piece of reusable code is called a function, they take a set of arguments, work on the specific problems that they are designed to solve, and let you know the results. I have often felt that our thought processes in our minds align with this. If I am to take a very simple example, when visiting a store, if I spot a pair of shoes that costs xxx$, the first thing that comes to my mind is — “Can I afford it?”

I feel that at this point I call a boolean function, isAffordable(xxx$, ‘shoe’) in the mind. The function factors in the money that I have this month, bills I have to take care of, and the projections of other expenses that might occur this month, the priority of the shoe among those things. So as a result, what I might get is the understanding of whether I can afford these shoes at this price this month. Everyone (Every system) has their way or their own implementations of this isAffordable() function. Now, most of my mental computations, checking if a particular thing is affordable might be making use of these functions. As our minds are much much complex systems, to me it is often impossible to reverse engineer many of my own thought processes.

While using the functions, there is a very interesting concept of a function calling itself, again and again. We call it the recursion. Many years back when I was working as a part-time instructor for the school children, at the time of the lab examinations, whenever students get a question on a recursion problem their expressions were very funny. Many of them have asked me whether they can provide the iterative solution rather than the recursive approach. Later in professional life, I have seen pieces of code where the iterative approaches were chosen to solve the problem where recursive solutions would have been much more elegant.

Recursive thoughts are very much common in our day to day life decision making. It comes in often in the cases where we have to make decisions on things that have dependencies. For instance, when you think if you can afford a trip it usually comes with a lot of dependencies, starting with whether you can afford 10 days of leave, skipping certain meetings in those 10 days, travel tickets, travel gears, health conditions, and much more. When we process every single dependency to see if it’s affordable, we might have to evaluate the dependencies of these dependencies are affordable and so on, until we reach a point where we can find a thing with no more dependencies from where we can wind back. Now, this is asking ourselves over and over until we find the solution to the problem that we are trying to solve. The larger the dependency tree for certain decisions, the more complex is the decision making procedure.

Now, if you have learned programming in school you might have written your first recursive function to print the Fibonacci series or computing the factorial of a number. These problems are very natural to be solved as recursive solutions, as their very own definitions contain recursion with them. Let’s take another small problem to take a look at recursion, this is also a problem that you are familiar with from the programming lessons from the school.

To check whether a string is a palindrome or not.

By definition, palindrome denotes if a string is the same even if it is read backward. A classic example of this is the word “MADAM”. My favorite example would be “MALAYALAM” which is my mother tongue. Let’s try different approaches to solve this problem.

A straightforward approach would be

A palindrome string is a string which is the same even if it is read from right to left
If a string is reversed and the reversed string is equal to the original string, well its a palindrome

Now looking at this solution, we can think of other ways of solving this problem. That is one of the beauties of the area of my work, there are so many different ways to solve a problem.

Now let us think in this way — If I iterate from the front and back of the string at the same time picking and comparing one character from both ends and if all the comparisons return true then I know the left side of the string mirror matches the right side of the string which tells us the string is a palindrome.

Shall we try to take a recursive approach to solve this problem?
Let’s remember all the answers you seek lie within you.

Let’s have a function isPalindrome() that takes in a string and tells you whether it’s a palindrome or not. Then inside the function, let’s take off the first and last letters of the string , check whether they are the same, and ask again the function if the rest of the string is palindrome or not; and let’s do this again and again until it reaches the central point.

At the central point, either there are two characters left (if the total number of characters in the string is even) or there is only one character. If there is only one character, we know for sure that it’s a palindrome as it is read the same from left to right or right to left. Now if there are two characters left and if they are equal, its palindrome(example: gg).

Well, that’s all!

We check the first and the last character of a given input is the same and we check if the rest of the string is a palindrome and we have arrived at our solution

Let’s take one more example, this is one of my favorites. This problem is called “The height of binary tree” A binary tree is a data structure where for every node, the number of children is no more than two. This is a classic data structure that we can use in a lot of decision-making process that involves yes or no answers for a node and the decisions take us to another node involving other decisions.

Here, the height of a tree represents the length from the root node to the farther leaf node. In this example, this will be the end option with the most number of decisions to make. If the decisions are weighted, the height of the tree can denote the maximum weight that can incur in any decision path. Let’s imagine there is some amount of time involved in making each decision then in the above example the most time-saving decision is to not make the snack and the most time-taking decision is to contact an independent reseller or Uber

How do we calculate the height of a binary tree? In the recursive approach, it’s rather simple. When we are at a node we take the largest of the height of its left subtree and the right subtree and since we are already at a node we add 1. When the tree has reached its leaf nodes when there are no more decisions to make we know the height of the leaf node is 1. Well, that’s all. We travel from the root node to the leaf node looking for the height asking the same question to each node but recursive.

Memorising the results

One problem that I have is “Overthinking” I know a lot of friends who have the same problem. This is a mental state where you place yourself in a position and imagine things that are even near to impossible and keep worrying about them. While the process is very unhealthy and absolute trouble, the only good thing that comes out of it is that in one out of a hundred times if you are in a situation (probably a surprising one)and if you have already thought through it you can make use of the results of that thought. Similarly, in the case of recursion, we call the same function over and over with varying arguments. Sometimes, the set of arguments to the functions might have already been evaluated in the past. Then we can make use of the results if we have memorised it

Here, the “memory” stores the results of the computation and there will be significant improvements on performance over memorising it Vs Not memorising it.

There are certain problems in life, they appear to be complex, the solution might seem very very far but it is much more nearer if you seek the answer within yourself.