Functional Programming - Lots of emphasis on recursion, why?

I am getting introduced to Functional Programming [FP] (using Scala). One thing that is coming out from my initial learnings is that FPs rely heavily on recursion. And also it seems like, in pure FPs the only way to do iterative stuff is by writing recursive functions.

And because of the heavy usage of recursion seems the next thing that FPs had to worry about were StackoverflowExceptions typically due to long winding recursive calls. This was tackled by introducing some optimizations (tail recursion related optimizations in maintenance of stackframes and @tailrec annotation from Scala v2.8 onwards)

Can someone please enlighten me why recursion is so important to functional programming paradigm? Is there something in the specifications of functional programming languages which gets "violated" if we do stuff iteratively? If yes, then I am keen to know that as well.

PS: Note that I am newbie to functional programming so feel free to point me to existing resources if they explain/answer my question. Also I do understand that Scala in particular provides support for doing iterative stuff as well.

Solution 1:

Church Turing thesis highlights the equivalence between different computability models.

Using recursion we don't need a mutable state while solving some problem, and this make possible to specify a semantic in simpler terms. Thus solutions can be simpler, in a formal sense.

I think that Prolog shows better than functional languages the effectiveness of recursion (it doesn't have iteration), and the practical limits we encounter when using it.

Solution 2:

Pure functional programming means programming without side effects. Which means, if you write a loop for instance, the body of your loop can't produce side effects. Thus, if you want your loop to do something, it has to reuse the result of the previous iteration and produce something for the next iteration. Thus, the body of your loop is a function, taking as parameter the result of previous execution and calling itself for the next iteration with its own result. This does not have a huge advantage over directly writing a recursive function for the loop.

A program which doesn't do something trivial will have to iterate over something at some point. For functional programming this means the program has to use recursive functions.

Solution 3:

The feature that brings about the requirement that you do things recursively is immutable variables.

Consider a simple function for calculating the sum of a list (in pseudocode):

fun calculateSum(list):
    sum = 0
    for each element in list: # dubious
        sum = sum + element # impossible!
    return sum

Now, the element in each iteration of the list is different, but we can rewrite this to use a foreach function with a lambda argument to get rid of this problem:

fun calculateSum(list):
    sum = 0
    foreach(list, lambda element:
        sum = sum + element # impossible!
    )
    return sum

Still, the value of the sum variable has to be altered in each run of the lambda. This is illegal in a language with immutable variables, so you have to rewrite it in a way that doesn't mutate state:

fun calculateSum([H|T]):
    return H + calculateSum(T)

fun calculateSum([]):
    return 0

Now, this implementation will require pushing to and popping from the call stack a lot, and a program where all small operations would do this would not run very quickly. Therefore, we rewrite it to be tail recursive, so the compiler can do tail call optimization:

fun calculateSum([H|T], partialSum):
    return calculateSum(T, H + partialSum)

fun calculateSum([], partialSum):
    return partialSum

fun calculateSum(list):
    return calculateSum(list, 0)

Of course, if you want to loop indefinitely, you absolutely need a tail recursive call, or else it would stack overflow.

The @tailrec annotation in Scala is a tool to help you analyse which functions are tail recursive. You claim "This function is tail recursive" and then the compiler can tell you if you are mistaken. This is especially important in Scala as compared to other functional languages because the machine it runs on, the JVM, does not support tail call optimization well, so it is not possible to get tail call optimization in Scala in all the same circumstances you would get it in other functional languages.