Elixir - Recursion


Advertisements

Recursion is a method where the solution to a problem depends on the solutions to smaller instances of the same problem. Most computer programming languages support recursion by allowing a function to call itself within the program text.

Ideally recursive functions have an ending condition. This ending condition, also known as the base case stops reentering the function and adding function calls to the stack. This is where the recursive function call stops. Let us consider the following example to further understand the recursive function.

defmodule Math do
   def fact(res, num) do
   if num === 1 do
      res
   else
      new_res = res * num
      fact(new_res, num-1)
      end
   end
end

IO.puts(Math.fact(1,5))

When the above program is run, it generates the following result −

120

So in the above function, Math.fact, we are calculating the factorial of a number. Note that we are calling the function within itself. Let us now understand how this works.

We have provided it with 1 and the number whose factorial we want to calculate. The function checks if the number is 1 or not and returns res if it is 1(Ending condition). If not then it creates a variable new_res and assigns it the value of previous res * current num. It returns the value returned by our function call fact(new_res, num-1). This repeats until we get num as 1. Once that happens, we get the result.

Let us consider another example, printing each element of the list one by one. To do this, we will utilize the hd and tl functions of lists and pattern matching in functions −

a = ["Hey", 100, 452, :true, "People"]
defmodule ListPrint do
   def print([]) do
   end
   def print([head | tail]) do 
      IO.puts(head)
      print(tail)
   end
end

ListPrint.print(a)

The first print function is called when we have an empty list(ending condition). If not, then the second print function will be called which will divide the list in 2 and assign the first element of the list to head and the remaining of the list to tail. The head then gets printed and we call the print function again with the rest of the list, i.e., tail. When the above program is run, it produces the following result −

Hey
100
452
true
People
Advertisements