![]() Before returning, the tail-recursive function needs to reverse the list, because the values get prepended to the accumulator. The first uses Enum.filter/2 and Enum.map/2 to iterate over the list twice, the second is body-recursive and the last is tail-recursive. Like before, we have three implementations. This example is a lot like the example we've seen before, but instead of adding all numbers together and reducing them to a single number, the double_numbers/1 function doubles all numbers and returns them in a list. reverse () end defp do_double_numbers3 (, acc) do acc end defp do_double_numbers3 (, acc) when is_number (head) do do_double_numbers3 (tail, ) end defp do_double_numbers3 (, acc) do do_double_numbers3 (tail, acc) end map ( fn n -> n * 2 end ) end def double_numbers2 () do end def double_numbers2 () when is_number (head) do end def double_numbers2 () do double_numbers2 (tail) end def double_numbers3 (list) do list |> do_double_numbers3 () |> Enum. That's often true when mapping over a list, where the function takes a list and returns a list without reducing it to a single value.ĭef double_numbers1 (list) do list |> Enum. While tail-recursive calls are usually faster for list reductions-like the example we’ve seen before-body-recursive functions can be faster in some situations. In fact, that's one of the 7 myths of Erlang performance. 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. 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. ![]()
0 Comments
Leave a Reply. |
Details
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |