To Find Out What Recursion Does, Just Find Out What Recursion Is Doing.

Recursion represented in the form of squares.

I’m writing today about a touchy subject in the programming community. I wouldn’t necessarily say it’s a love-hate relationship, because I really don’t hear much love being tossed around for it. I have heard several of my peers agree on one thing though; the harder one tries to dissect what recursion does, the more confused one is about what recursion is actually doing.

This may all sound confusing because it is. The fact is, recursion is just all-around hard to explain, not to mention, nearly impossible to keep track of in a literary sense. So, what better way to describe the process of recursion than with a… wait for it, can it be?? A PICTURE!!!? That’s right big kids!! I’m taking things back to a better time when pictures were the best part of, well, everything!

For the picture to make sense, I’ll first provide some need-to-know:

  • A recursive function is a function that calls itself.
  • This example is a recursive function that calculates the power of x to the yth
  • x = a number
  • y = the exponent (how many copies of x to multiply together)

Keep in mind that recursion may not always be the most efficient way of tackling a problem. If put in a situation where the function is calling itself upwards of hundreds of times, the execution time would be insurmountable. Not to mention the potential risk of causing a stack overflow, if a Base Case is not established. So, be conscious of the Big O time complexity and knowing that the worst-case scenario could be O(n²) before making any rash decisions to use this method. However, that’s another topic, for another day and so I’ll leave it at that! Remember you can always learn more! Play around with new concepts and never be scared to RTFM’s and find out from the true source! :)

I’ve made this non-text object with the intention of creating a visual sensory experience, but if pictures aren’t your thing, stick around afterward while I attempt to describe what is happening in each step! :)

Step by step look at a simple recursive function!
  1. X and Y are both assigned the value of 2, and passed in as arguments to the _pow_recursion() function.
  2. The arguments are evaluated to see if it meets the **Base Case, which will be if y is equal to zero. Since y is 2 and not zero, we will continue on to step
  3. Check to see if y is a negative number. If yes, skip step 5. If no, skip step 4.
  4. Evaluate the recursive case by adding it to the stack, then repeating the process over from step 1!
  5. Evaluate the recursive case by adding it to the stack, then repeating the process over from step 1!

**BASE CASE:

When reaching the Base Case, in other words, y is equal to 0. The function returns 1. This, in turn, will proceed to “pop” the rest of the recursive calls off of the stack. It does this by inserting the return value of 1, into the most recent recursive case that was added to the stack. This process cascades through the rest of the stack, giving a final return value of 4.

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store