Erlang: Recursion vs. Lists

Question

I'm new to Erlang, and I'm trying to figure out why recursion is faster than using a list (which might even get the error “cannot allocate memory in a heap”).

I created two functions for finding prime numbers for a value (fairly straightforward):

• using recursion:

  find_factor_rec(List, Max, _, NextValue) when NextValue > Max -> List; find_factor_rec(List, Max, Value, NextValue)-> if (Value rem NextValue =:= 0) -> find_factor_rec([NextValue|List], Max, Value, NextValue + 1); true -> find_factor_rec(List, Max, Value, NextValue + 1) end . find_factors(Val)-> find_factor_rec([], round(math:sqrt(Val)) + 1, Val, 2). 

• list

   find_factors1(Val) -> [X || X <- lists:seq(2, round(math:sqrt(Val)) + 1), Val rem X =:= 0]. 

while I'm missing small values ​​- both at the same time. When I pass in huge values, such as 403851455234578, the second function got slower and slower and even throws an error.

Can someone explain why the first function is better than a list? Is there a better way to rewrite a function? Is there any naming convention for the first listing? (function plus their "recursive functions")

Thanks.

Answer 1

The first function is faster because you only calculate the top number once. In the second function, you create all numbers from 2 to the square root plus one. The integers 20096056 are listed.

 lists:seq(2, round(math:sqrt(Val)) % Creates a list from 2 to 20096056 

Your problem is not suitable for a solution that creates all the search space in memory due to lack of space and performance.

In conclusion, the use of lists here is very unproductive.

---

As for naming conventions: when a function has a different arity (a different number of arguments), it usually calls it the same. Erlang does not consider it the same function, although functions with the same name and arity are considered equal.

 find_factors(Val)-> find_factor_rec([], round(math:sqrt(Val)) + 1, Val, 2). find_factors(List, Max, _, NextValue) when NextValue > Max -> List; find_factors(List, Max, Value, NextValue) -> if (Value rem NextValue =:= 0) -> find_factors([NextValue|List], Max, Value, NextValue + 1); true -> find_factors(List, Max, Value, NextValue + 1) end.