Back
Close

Functional Programming explained to my grandma

Anne-Honyme
4,722 views

Recursion

One does not simply talk about functional programming without saying the word "recursion".

The first question I asked myself is: Why use recursion? I was bad in mathematics, and I hated coming across recursion.

But we can ask the question the other way around: Why should we use loops?

Loops are the consequence of iterative design: we go from one step to another. In lower level languages, we have to define the number of steps we want to run without any real proof that this number is the right one.

With recursive calls you can be sure that you will stop at the end, and you won't need to know the exact number of steps it will take. Whatever this number is you will perform your operations at each step and stop when your end condition is hit.

However, as seen in the previous exercise, a high order function can use another function and by extension, itself. THerefore, recursion is a core feature of a pure functional language.

Let's try a simple exercise to refresh our memory. Implement a method which returns a list filled with the x first elements of the Fibonacci sequence.

Implement the Fibonacci sequence

With this first example, we keep every element in the stack to rebuild the full list at the end. We can do better by using tail recursion.

Tail recursion is a way to build recursion where we don't need to keep each and every step in order to return the final result. The last thing you will do is call this function. The common way to do that is to use an accumulator.

An example of tail rec:

def factorial(n: Int): Int = {
  def iter(x: Int, result: Int): Int =
    if (x == 0) result
    else iter(x - 1, result * x)

  iter(n, 1)
}

Let's try to modify our Fibonacci sequence to be a tail recursion

Implement Fibonnaci as a tail recursion

The Scala compiler optimizes tail recursion, so we should definitely use it.

One last tip, the @tailrec annotation DOESN'T FORCE TAIL RECURSION. During compililation, it verifies that you are using tail recursion.

Create your playground on Tech.io
This playground was created on Tech.io, our hands-on, knowledge-sharing platform for developers.
Go to tech.io
package example
import scala.annotation.tailrec
/**
* Created by charlotte on 06/05/17.
*/
object Recursion {
/**
* Implement an algorithm which returns a list with the X first elements of the Fibonacci sequence ,
* from bigger to smaller
* @param list the previous elements (empty list at first call)
* @param size the number of elements you want
*/
def fibonacci(list : List[Int], size : Int): List[Int]= ???
/***
* implement an algorithm which returns a list with the X first elements of the Fibonacci sequence ,
* from bigger to smaller with tail recusion
* @param size the number of elements you want
*
*/
def tailFibonacci(size: Int): List[Int]= ???
}
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
codingame x discord
Join the CodinGame community on Discord to chat about puzzle contributions, challenges, streams, blog articles - all that good stuff!
JOIN US ON DISCORD
Online Participants