Tail Recursion for Sum - Elixir

Question

I'm new to both Elixir and tail recursion.

defmodule MyInteger do
 defp sum_upto(x, accumulator) when accumulator <= 1 do
 accumulator
 end
 defp sum_upto(x, accumulator) when accumulator > 1 do
 sum_upto(x, accumulator-1) + accumulator
 end
 def sum_upto(x) when x <= 1 do
 x
 end
 def sum_upto(x) do
 sum_upto(x, x-1) + x
 end
end

Is the above an optimal way to calculate the sum up to x?

• Jörg W Mittag: I'm not sure what you mean by "optimal", but what I am sure about is that your solution is not tail-recursive: the tail call is to +, not sum_upto. It's hard to see with infix operators, imagine instead, you had to write everything as a function call: plus(sum_upto(x, accumulator-1), accumulator) Now it's trivial to see that the tail call is to plus, not to sum_upto, IOW that the recursive call is not in tail position.
• Mouli: @JörgWMittag Thanks. Makes sense that it's not actually tail-recursive. Based on your comments, edited code, and looks like this should be fine: defmodule MyInteger do def sum_upto(x, accumulator \\ 0) do if x == 0 do accumulator else sum_upto(x - 1, x + accumulator) end end end

Answer 1

Overview

I see that there are some good comments and I thought I'd just explain in a full answer block -- I'm not on here too often so I apologize for the tardiness of the response. Bear with me as I first show you what I might really do then demonstrate the answer to your tail recursive question using the same terms with which you posed your question.

What I Would Do

First, I think you are asking how to add up the numbers 1,2,3,...,x.

I would actually use the Enum.reduce function:

1..20 |> Enum.reduce(0, fn(x,acc) -> acc + x end)

or using Elixir capture syntax which is more concise and obtuse:

1..20 |> Enum.reduce(0, &(&1 + &2))

The Main Question

Now to the crux of your actual question, how would I do this without using Enum and using tail recursion. First note that the last entry in the function call will be the function itself. There must be no other add, sub, multiply, -- operation of any kind before or after the function call. You can change the parameters but don't do anything outside call itself.

Here is a simple tail recursive routine that adds numbers up:

defmodule MyInteger do
 def sum_to_x(0, acc) do
 acc
 end
 # initial function call
 def sum_to_x(x, acc) do
 sum_to_x(x - 1, acc + x)
 end
end
IO.puts MyInteger.sum_to_x(20, 0)

I wrote this counting down to make it like your example. When you first call MyInteger.sum_to_x(20, 0) the second form of the sum_to_x function is used. We pass 0 as the initial value of the accumulator. The last line in that function calls itself and nothing else (tail recursive). That is when the function finally "returns" there are no other ops to do. This function will call itself counting x down until x is zero. When is is zero, we match the first form of the function since we have a "0" in the first parameter. This form just returns the accumulated result --

uDude