Since I took a step back I decided to take my time. I have a lot of work to do before I get comfortable with the concept of recursion. While I was writing a super simple example function I panicked and thought I had messed it up. That really made me realize how much I need to cover. Today was just setting the foundation. I started up on writing notes again since this topic is something I have covered before but am now trying to formalize in my mind. Trying to solve an algorithm is messy so I stopped writing notes on it. However, I have had to repeatedly look up concepts regarding recursion so I figure it is worth noting down. One thing that is great is that I have already built the infrastructure to support my note-taking on this topic. My folders are already organized which feels great. I literally just had to jump in.

TLDR;

Okay, so here are the highlights of what I did:

• Still reading through the book “Cracking the Coding Interview” by Gayle Laakmann McDowell. Still working on the practice problems. Stuck on question eleven. I decided to focus on re-learning the concept of recursion and build up some notes full of example algorithms before re-attempting this problem. I do not think I should have gotten this question wrong and so I need to try my best to prevent this form happening again.

Notes on Recursion – Work in Progress

Recursive Runtimes

When analyzing recursive algorithms we have to take a logical approach in stepping through the code. There are two key components I have noticed in all recursive algorithms.

1. A base case
2. A logical trigger for the recursive call

The Base Case

The “base case” is what will happen when a conditional that prevents another recursive call is triggered. For example:

// Adds all the values between 1 and n 

int sum(int n){
  if (n <= 0){
    return n;
  }
  return n + sum(n - 1);
}

• The base case is when n is less than or equal to 0. In that scenario the value of n alone will be returned. Based on the example our base case is when n = 0. Note: Although this is the base case our calculation actually ends when n = 1 since adding 0 does not change the sum.
• The trigger for the recursive call is the goal of adding all the values together. The initial call states that we wish to add the value of n with all the values between n and our base case. Therefore the function is repeatedly called with n-1 values until that base case is met.

The Trigger For Recursion

A recursive function in most cases does not exist just for the sake of being a recursive function, it exists to serve a purpose. If we keep that in mind we can understand the logical progression that takes place in order for the function to call itself repeatedly to complete a task. This logic is the core concept needed to grasp the trigger for recursive calls. In the previous example:

// Adds all the values between 1 and n 

int sum(int n){
  if (n <= 0){
    return n;
  }
  return n + sum(n - 1);
}

We wanted to add all the values in-between n and 0 (inclusively). This could arguably been accomplished using a for loop. However, because the same action would be performed repeatedly an opportunity to utilize a recursive function was presented. The repeated action would be addition in this example.

Therefore if we are ever dealing with a recursive function that is difficult to comprehend, we can manipulate the algorithm and try to re-represent it without the use of the recursive call and instead try to use a for loop. Note: This may not work in all cases. I am simply trying to present potential solutions that I can try in the future.

Recursion Trees

In more complicated recursive algorithms the initial call to a function can trigger multiple recursive calls that produce numerous branches / chains of recursion. I am terming these branches / chains as “Recursion Trees”.

Conclusion

That’s all for today. If you are interested in the MIT course you can check out the video lecture I’m currently going through. The lecture is helpful but isn’t sufficient by itself. Anyways, until next time PEACE!