A World Without Loops

A Tale on Recursions

Photo by Steve Johnson on Unsplash

Introduction

Working with imperative languages has made it feel almost impossible to think outside loops — for, do while, etc

And most programs are built that way because a lot of our human interaction needs certain conditions to be fulfilled to make certain triggers. This is especially important because the circumstances aren’t always perfect or fixed if we are to scale for millions or even billions of users.

A World of Loops

Loops (hackernoon)

An excerpt from here:

We use iteration by repeatedly executing a set of instructions until the terminating condition is hit. If the terminating condition doesn’t get hit, then it’ll lead to an infinitive loop. An infinite loop will waste precious CPU cycles.

On the other hand, we write a recursive function by defining a base step and an inductive step. The base step evaluates a terminating condition and returns without calling itself, whereas the inductive step calls itself with different argument values. If we never hit the base step’s condition, then it will make the recursive function infinite. Infinite recursion can easily crash the system by consuming all the available memory.

Recursions (hackernoon)

Manipulating Lists

In going through a list one thing is obvious we will have to sometimes loop through it. Say you have to go through a list and add all the values or filter through a loop to apply certain expressions or sort values that satisfy a required condition you might most always need a loop.

Let’s look at an example:

const scores = [22, 54, 76, 92, 43, 33];

for (let i = 0; i < scores.length; i++) {
    console.log(scores[i]);
}

The example above is that of a for-loop, which prints out every element in the list. The for-loop declares a variable i which is equal to zero.

i is also declared to be less than the length of the list “score” as a constraint and after each iteration, it checks if the condition is not fulfilled thus i++ act as the increment operator to ensure that the variable i increases to fulfill the condition i< scores.length. This forms a loop that will only break when the condition is fulfilled.

The danger of the above is such that a mistake on the constraints in a lot of cases leads to an infinite loop.

A look at a recursive function

A recursive function definition gives the function in terms of itself. Here the example code is written is haskell. It would look something like this:

reverse' :: [a] -> [a]  
reverse' [] = []  
reverse' (x:xs) = reverse' xs ++ [x]

The reverse function is a common function in haskell that reverses the element in a list.

In the first line the types are declared.

In line 2 the first base condition states that if it is an empty list, then the result should be an empty list. But if it is not an empty list then line 3 is implemented:

(x:xs) — the sign : is called a cons it can be used to deconstruct a list or link a list. In the case x:xs it separates the list into the head element and the tail.

Note: A list [1,2,3,4,5,6] is such that [1] is the head and [2,3,4,5,6] is the tail.

So x:xs would mean [1] : [2,3,4,5,6]

In the case of line 3 of our recursive function above, the function calls itself on the right hand side, and with each call it deconstructs the head of the list repeatedly and attaches it on the end until the list is reversed. In recursions functions can call themselves or act on themselves repeatedly.

Example 2:

What if we try to write a snippet of code that counts the number of times an elements appears in a list. Well it would look interesting too. Something like this:

elemCount :: Eq a => a -> [a] -> Int
elemCount x [ ] = 0
elemCount x (y:ys)
          | x == y = 1 + elemCount x ys
          | otherwise = elemCount x ys

Line 1: Declares the types. It takes is a polymorphous type “a”, compares it with a polymorphous list and outputs an integer.

Line 2: A base condition that if the element x is checked against an empty list then it would output 0.

Line 3: If the list is not empty then the function checks some conditions that if x equals y at anytime then count 1 and call the function again in line 4, otherwise it just checks the list without adding 1.

This way we are able to output the number of times an element appears in a list or an array as some languages call it. This makes haskell very beautiful to look at and some functional languages are able to deal with loops using the approach of recursions.

Loops vs Recursions

Recursion works at the method or the function level, whereas looping is applied at the instruction level.

• A recursion makes it possible to write shorter or simpler codes unlike a loop.
• It can be reasonably assured that the depth a recursive stack would not lead into a stack overflow except it becomes too long.

An excerpt from a stack overflow user says:

In a programming language that is not functional, an iterative approach is nearly always faster and more efficient than a recursive approach, so the reason to use recursion is clarity, not speed. If a recursive implementation ends up being less clear than an iterative implementation, then by all means avoid it.

A Quora user(Divy Satyam) says:

Recursion is a better way of solving a problem as compared to looping .In most cases time complexity of a recursive solution is better than the loop one. Most of the software company in their interviews prefer a recursive solution.

Surya Karuna on Quora adds:

It depends on the problem, mostly recursion reduce our efficiency, but it may reduce the line of code, so i preferred looping

Another person adds:

obviously recursion

although there is not much difference at the view level but recursion is faster than the iteration…

Another user adds:

Recursion has some overhead because you are making function calls again and again and each function call requires some sort of memory allocation which creates both space and time overhead. But this is negligible in most of the everyday programs.

Finally someone else says:

To my view, recursion will be better because immutability can be achieved easily and also incase of tail recursion it runs on a constant stack memory.

Conclusion

In the end either ways we decide to compare them they both have their pros and cons and depending on the problem the context can decide the best fit.

Thanks for reading, I do hope you enjoyed the simplicity please like.

Otobong Peter