for loops and while loops have long been the programmer’s best friends, allowing them to repeatedly perform actions under a condition or to iterate over a list or array. Whether it be reading a feed, tokenizing input, or simply looping over an array, iterative programming has been the go-to method for ages.

History of Iterative Programming

Iterative programming took roots long ago, at the dawn of modern programming.

Fortran is known as one of, if not the, oldest programming languages still in use today. The language, created in 1957, possesses imperative and iterative principles. As one of the first programming languages, its style played a massive role in the construction of future programming languages, such as the secure Ada, which possesses its structure, and the renowned, powerful C, which shares its imperative nature.

As an imperative language, Fortran possesses both while constructs and mutability, or the ability to reassign values to variables and other data structures. This allows for looping within a function to be possible, enabling the ability to iterate over structures.

Hence, iterative-style programs, such as this one that calculates factorials in C, became popular:

unsigned int factorial(unsigned int n) { 
    int res = 1, i; 
    for (i = 2; i <= n; i++) {
        res *= i; 
    }
    return res; 
}

But what if mutability is not available?

Recursive Programming

Recursive programming is a method where problems are solved by repeatedly calling a function on sub-instances of the problem. It allows the programmer to perform the same operations as available in iterative programming while avoiding mutable values and loops through calling a function from within itself with modified arguments.

A paradigm that commonly makes use of recursive programming is functional programming, a style that involves building programs as evaluations of mathematical functions without changing both state and data.

Haskell is, according to their website, “an advanced, purely functional programming language.” Rooted in mathematics and adhering strongly to the functional principals, it includes no modifying state or reassigning of variables. One of the most popular of the functional language groups, it is accompanied by other greats such as the battle-tested Erlang and industry-strength OCaml.

Let’s take a look at recursive programming in Haskell. Without the ability to reassign variables, how can we modify nfact and n each time in the loop? And, without a while construct, how do we loop?

The answer is writing a program where a function calls itself with modified outputs over and over again to achieve a final answer. With that in mind, here is how to calculate factorials in Haskell:

factorial :: Int -> Int
factorial 0 = 1
factorial n = n * factorial (n-1)

If the value is 0, it returns 1, because the factorial of 0 is 1. Otherwise, it returns the value of n*factorial(n-1), walking downwards in value until n is zero, like how humans think about calculating factorials!

However, functional programming is also available in most non-functional programming languages, including C. Here is a functional-style factorial function written in C:

unsigned int factorial(unsigned int n)  { 
    if (n == 0) {
        return 1; 
    }
    return n * factorial(n - 1); 
}

Iteration vs. Recursion

After a look into both iterative and recursive programming, you have likely realized that the two styles can accomplish the same things. Some languages, usually imperative languages, support both iterative constructs and recursion, while functional languages typically only support recursion.

So why use one or the other?

Iteration is preferred by most programmers in non-functional languages because it provides easy access and reading of the loop controls and internals, as they are all located in one block of a function. Also, many languages that support loops optimize them to run faster than recursion in the same language.

Recursion is preferred by most functional programmers and those who write compilers and interpreters because tree walking is much more straightforward in recursive programming. Also, mathematical functions are better represented in recursion as it sticks closer to the mathematical definition (look over the factorial functions, for example). Tree walking is the traversal of a branched data structure, such as an abstract syntax tree, which represents a program in a compiler.

In the end, in a language that supports both recursion and iteration, it comes down to preference and the test at the end. Iteration provides a little extra speed and memory safety for less understandable code, while recursion provides more elegant programs but requires the programmer to be aware of the depth of recursive (to prevent stack overflow).

But wait! There is one more component to recursive programming that can yield benefits to the programmer.

Tail Call Optimization

A tail call is a function or routine performed as the final action of another function or routine. If the tail call calls its parent function, the function is deemed a tail-recursive function. Tail calls in recursion allow the compiler to jump back to the top of the function without allocating a new stack frame, which reduces the risk of errors such as stack overflow.

Stack overflow is when the call stack, which a program uses to keep track of subroutines, exceeds its bounds. In a language without tail optimization, using recursion for functions like factorial(INT_MAX) can cause this.

Most functional languages guarantee tail call optimization, a procedure where the compile can recycle the function’s previous stack frame for use in the next recursive execution. This preserves memory and can even increase the speed of the function’s execution.

Therefore, in languages that support tail call optimization, recursive methods receive the ability to have a performance boost over iterative programming.

Wrap-Up

Though iterative programming has been the go-to for many programmers, both beginner and expert, for a long time, recursive programming offers developers a new way to go about functions in a way that can potentially provide optimization and increased program readability.

When presented with a choice, remember to take into account the benefits that one method of programming may have over another so you can achieve the best possible program.

Source: medium