Sold to

imteyazmohsin@gmail.com
What is recursion? What is? What? 🔄
Recursion is a coding loop technique where the function created repeatedly calls itself
until a certain condition becomes true. By then, the last called function returns the entire
evaluation. (More on this later).

DISCLAIMER: It is one of the most confusing programming techniques I’ve ever come
across and have had to explain so far, but here goes…

What is the purpose of recursion?

But…

Where you sacrifice for cleaner code, you pick up the chances of your code becoming
more confusing to understand.

How does a function work?

When you use another function in your function to get a value, let’s say from a helper
function, you are asking for the evaluation of what that function has processed.

The code will NOT move forward until that function you’ve called now evaluates. I
emphasize the importance of understanding this part.

Sold to
imteyazmohsin@gmail.com
Call Me, Definitely.
If a function is called, and it is not fully evaluated, it gets stored in a stack. Specifically,
it’s called the call stack. Stacks as we know it follow the LIFO principle. The last function
to be called will be the first to be evaluated

So how is recursion working?

Again, When you call a function in which you are returning a value, that function has to
fully evaluate in order to provide the value. Let’s break down a simple function
add(num1, num2):

As you can see, because 1 & 2 are primitive data types that just need to be added
together, this can be evaluated easily to 3, which is then returned for you to store in a
variable

But what about the function factorial(num) which multiplies numbers in descending
order all the way to 1?

We start by initializing a variable total. In the for loop, we start with the total being 3,
then multiply that by i, which starts at num - 1, or i = 2. Finally we’ll multiply the new
total by 1. The loop then exits before we get to 0, to which we return the total.

Sold to
imteyazmohsin@gmail.com
This works, and in this case, I would say use this method.

Recursively, here’s how we would write the same function:

The function works the same but a different process is happening.

If that’s too confusing to follow this with newNum, just know you can pass in the same
num -1 into the newly called function:

We start with the number 3. The function first checks if the number is 1 or 0 before
commiting to the recursion. This is called the base case. This tells the function what to
return to the other previously called functions. It also helps to prevent the function from
infinitely calling itself.

Because 3 isn’t 1, we tell the function to now return to us what 3 * the descending
number is (num - 1) or (2)

Sold to
imteyazmohsin@gmail.com
The Factorial (3) function hasn't been evaluated fully because it needs the results of
Factorial (2) to evaluate, so Factorial (3) is now on hold. In Factorial (2), the same
process has to happen because 2 obviously isn’t 1. This leaves us with 2 * Factorial (1)
and with 2 functions in our call stack.

Now that we’re in Factorial (1), our base case says what to do if we get the number 1,
which means to just return 1. Factorial (1) has been fully evaluated. It can now return
the evaluation back to Factorial (2).

Back up to returning 2 * Factorial (1) we now know it’s to return 2 * 1 which is just 2.

We’ve fully evaluated factorial(2)

Finally, we’ve come back to the original request, Factorial (3), which asks us to return 3 *
Factorial (2), or 3 * (2). Within a couple of recursive steps, we’ve evaluated that
Factorial (3) returns 6.

It’s extremely hard to see how recursion is working without a true understanding that
functions MUST evaluate fully before returning a value.

Here’s how that looks in the call stack:

Sold to
imteyazmohsin@gmail.com
Why would I ever use this?!
It’s rare you’ll be using recursion for a problem as simple as this. It’s neither good nor
bad to use either recursion or traditional loops, since on average they both take the
same amount of time to complete.

Although if you can get away with using a for or while loop, try to use a for loop when
you know how many iterations to run, and a while loop when you don’t. These loops are
also a tad better in overall performance.

Still, there are cases where recursion would be the best option to get an evaluation.

In linear data structures like linked lists, queues, and arrays, for loops and while loops
will be most efficient to set up.

However, in more complex, repetitive problems, recursion will be the best answer.
Recursion also works best with hierarchical and unordered data structures like Trees,
file directories, and graphs.

Sold to
imteyazmohsin@gmail.com
Preventing Stack Overflow
I mentioned that if not properly defined, recursive functions will infinitely run. Infinitely is
a misstatement. Unlike loops that will run forever and ever until you run out of memory,
the call stack does have a limit to how many functions can be in the call stack. When
you exceed this limit, (i.e. infinitely calling your function), you’ll get a Stack Overflow
Error.

This either means you didn’t set up a stopping point or it wasn’t set up properly.

Tracking your stacking

In your IDE, especially if you use VSCode, you have access to a toolset known as a
debugger. The debugger shows you the functions as they’re called and which functions
haven’t been processed.

The debugger also keeps a track of any variables and iterations each step of the way,
which will help you understand how your function is running and evaluation.

It is your first line of defense against stack overflow as well.

To use it in VSCode, hover over the far left of your code just past the line number. A red
circle should appear. This is called a breakpoint. Wherever you add this is where your
code will start the debugging process.

Once you do set your breakpoints, navigate to the icon in your panel that has a play
button and a little bug. From there you’ll see the green play button that has “Launch”
next to it. Use this to troubleshoot where your recursive function is going wrong.

Problems
If you made it this far, here are some problems that you can try to understand recursion.
They range from (relatively) easy to intermediate. Check out my Github Gist for
solutions to each problem.

Easy:
fibonacci(num): Write a recursive function to return the n-th Fibonacci number. Your
base cases are F(0) = 0 and F(1) = 1. For other numbers, F(n) = F(n-1) + F(n-2)

Sold to
imteyazmohsin@gmail.com
sumOfArray(array): Write a recursive function to find the sum of an array of integers.
Your base case is when the array is empty. Otherwise, sum is the first element plus the
sum of the rest of the array.

Intermediate:
reverseString(string): Write a recursive function to reverse a string. If the string is or
becomes empty, return the empty string. Otherwise, remove the last character and add it
to the front until all ending letters are up front.

* Note: reverseString prevents you from having to split the chars, reverse, then rejoin *

power(x, n): Write a recursive function to calculate x raised to the power of n. The base
case is where n = 0. For even numbers, use xn =(xn/2 )2. For odd numbers, use xn=x * x n−1.

Thanks for reading! And be sure to check out my future and previous works on my
gumroad!

🙂
If you liked the reading, please consider donating! It’s not required, but I am a currently
unemployed student who would just like to grab a coffee here and there

Sold to
imteyazmohsin@gmail.com