Recursive Functions in JavaScript

Recursive Functions in JavaScript

Image for postStop looking

What is Recursion?

In JS, and in coding in general, A recursive function is a function which calls itself. As an example, let?s look at using a recursive function used to calculate the factorial of a number, n. (A factorial being the product of a positive integer with all of the whole numbers lower than it; e.g: 4! = 4x3x2x1 = 24)

Image for postA function that computes the factorial of the number n by calling the function recursively within itself. (NB: My function would be improved if it tested for negative or non-integer arguments)

In the function above, the return statement contains a ternary (i.e. TrueOrFalseExpression ? returnIfTrue : returnIfFalse) that, if the number is not equal to one, will multiply the argument (n) by the return value of the the same function, but called with the argument n-1, i.e. one less than the original. Of course, this 2nd function call will do the same with a 3rd call, and the next the same, and so on and so on until the argument passed is equal to 1, and in this case the number 1 will be returned instead. So, if n=4 for example, our return statement will ultimately be evaluated to 4x3x2x1 === 24. More on how these ?nested? returns work in the Reversing a String example below.

Avoiding an Infinite Loop

You?ll notice that in the above example, we have an ?escape condition? for our recursion (the argument of factorial() will eventually ===1). Similar to loops (e.g. forloops), an escape condition is a requirement for all recursive functions!

Using Recursion to Replicate a While Loop

Image for postImage for postReplicating the functionality of a while (x ? 5) {x++} loop using recursion. The console output is on the right.

Above, you can see that the functionality of JS?s while loop can be replicated using recursion. Although I don?t know of any advantage to doing this, it?s interesting nonetheless.

Reversing a String

I?m not sure how useful this example would be in the real world, but it?s certainly one I?ve been asked in tech tests, and I wish I?d known how to use recursion to solve it!

Image for post

So, as with the factorial example above, our recursion logic can neatly fit within a ternary statement. In this case, our escape (aka ?exit?) condition checks if the argument passed into reverseString() will be “” and if so, an empty string “” is returned in kind, and the recursion stops.

When first called, reverseString() immediately calls itself, but with str.substr(1) as an argument {The substr() method, when given just one argument, simply returns a substring cut from the original: omitting a set number of characters from the front of the string, as stipulated by the integer value that?s passed as an argument}. So in the above example, the first character will be removed, giving ?eversed?. This is what is passed to the 2nd recursive call (i.e.reverseString(‘eversed’)) but what is returned from the first call is: reverseString(‘eversed’) + ‘r’

This 2nd reverseString() call is known as a ?nested? function call. And it is very important to note that the most nested function call returns first. So, to take a simpler example than reversing ?reversed?. Let?s try reversing ?yes? to explain this further. The nested returns would play out as follows:

Image for postSomewhat counterintuitively, the ?most nested? (here labelled 4th) return, is returned first. And so, we follow the blue arrows backwards up the nesting to get the ultimate return ?sey? (see bottom of image).

Note: In our factorial example above, the order that the nested returns were evaluated didn?t really matter, as multiplication is commutative. However, it?s important to understand it in this example.

2

No Responses

Write a response