rockhilt.blogg.se - Tail recursion

#TAIL RECURSION PLUS#

While the results of that benchmark look quite convincing, tail-recursion isn't always faster than body recursion.

The tail-recursive version was almost twice as fast ad the body-recursive one. In this test on this machine, we see that the body-recursive version is almost three times as fast as the original implementation that used Enum.filter/2 and Enum.reduce/3. Tail call optimization allows functions calling themselves without running into stack problems. Instead, it uses the current frame by jumping back up to the beginning of the function.

Finally, the exit clause returns the accumulator.īy calling itself at the end of the function and passing the accumulator with all calculated values, the Erlang VM can execute a trick called tail-call optimization, which allows it to circumvent adding new stack frames.

When the head is not a number, the third function head drops it by calling itself with the tail and the current accumulator, without changing anything.

It calls itself with the list's tail, and the head added to the accumulator.

Much like the previous example, do_sum_numbers3/2's first function head matches lists with a numeric head.

The sum_numbers3/1 function is the public function, which calls the private do_sum_numbers3/2 function with the passed list and an accumulator of 0 to start with.

It does so by keeping an accumulator ( sum) that keeps the current value instead of stacking function calls. However, this example is tail-recursive, meaning it doesn’t need to await a call to itself before continuing. This example is yet another implementation of the function from before. With a small rewrite of our code, we can prevent the stack frame being added and that memory allocated. To keep the memory footprint to a minimum, some languages-like Erlang and thus Elixir-implement tail-call optimization. Tail recursion and tail-call optimization Adding a stack frame to the call stack requires some memory to be allocated, and can cause some overhead. That’s because each item warrants a call to a function, which needs to be executed to claim its result.

#TAIL RECURSION PLUS#

Once for each item, plus once more for the empty list at the end.īecause the function calls itself for each iteration, each item in the list causes a stack frame to be added to the call stack. This list shows the how the function is simplified until we get to a result, which shows the function being called six times. This clause, also known as the termination clause, ignores the message argument by assigning it to the _msg variable and returns the atom :ok.Sum_numbers2 () + 1 + 2 Elixir then proceeds to try the next function clause, which explicitly matches on the case where n is 0. When the second argument is zero, the guard n > 0 evaluates to false, and the first function clause won’t execute. Then we print the message one last time and call print_multiple_times("Hello!", 0), starting from the top once again. Given the second argument, n, is still more than 0, we print the message and call ourselves once more, now with the second argument set to 1. Now we execute the same function again, starting from the first clause. Since this is the case, it prints the msg and then calls itself passing n - 1 ( 2) as the second argument. The first clause has a guard which says “use this definition if and only if n is more than 0”. When print_multiple_times/2 is initially called in the example above, the argument n is equal to 3. A particular clause is executed when the arguments passed to the function match the clause’s argument patterns and its guards evaluate to true. Similar to case, a function may have many clauses. print_multiple_times ( "Hello!", 3 ) # Hello! # Hello! # Hello! :ok puts ( msg ) print_multiple_times ( msg, n - 1 ) end def print_multiple_times ( _msg, 0 ) do :ok end end Recursion. Defmodule Recursion do def print_multiple_times ( msg, n ) when n > 0 do IO.