Tail Recursion chapter 2.5

perfect.erl

-module perfect.
-export [test/0].
-export [is_perfect/1].

test() ->
    true = perfect:is_perfect(1),
    false = perfect:is_perfect(2),
    false = perfect:is_perfect(5),
    true = perfect:is_perfect(6),
    false = perfect:is_perfect(24),
    false = perfect:is_perfect(25),
    true = perfect:is_perfect(28),
    % from https://en.wikipedia.org/wiki/List_of_perfect_numbers :
    true = perfect:is_perfect(496),
    true = perfect:is_perfect(8128),
    true = perfect:is_perfect(33550336),
%    true = perfect:is_perfect(2305843008139952128) <- don't try this at home. It took 105 sconds on my machine ;)
    ok.
    
% @doc is_perfect determines whether a number is 'perfect' in that the sum of its divisors adds up to itself.
    % The strategy is to identify divisors of the number, adding them up along the way, then finally comparing that
    % total to the number itself.
    %
    % The traversal to identify divisors will only need to operate up to the square root of the number, because
    % any divisor up to (and including) that point will have a 'matching' second divisor that is the
    % division of the number by that first divisor, so it is trivial to determine the second divisor without
    % needing to continue testing for divisors beyond that end point.

    % no need to recurse on the degenerate case of N=1; just return the result
is_perfect(1) ->
    true;
    
is_perfect(N) when N>1 ->
    N=:=sum_of_divisors(N,trunc(math:sqrt(N)),1,0).
    % NOTE: because math:sqrt will generate a Float which may not be calculated perfectly accurately,
    % this routine may not work correctly for certain extremely large values of N

% The parameters passed to sum_of_divisors/4 are:
%    N, the number being analyzed
%    Final, the last value being tested for divisibility
%    Counter, the incrementing value working up to Final, and
%    Total, the accumulated sum of divisors detected so far

%tail call: Stop when the Counter reaches the Final value.
% There are three distinct cases to handle when this occurs:

% The Final value of Counter is not a divisor of Number; return the final value of Total
sum_of_divisors(N,Final,Final,Total) when (N rem Final) =/= 0 ->
%    io:format("tail_neq:Counter=~p, Total=~p.~n",[Final,Total]),
    Total;

% The Final value of Counter is a divisor of Number, and is the exact square root; add just that one divisor to Total
sum_of_divisors(N,Final,Final,Total) when (N rem Final) =:= 0 andalso Final =:= (N div Final) ->
%    io:format("tail_eq_sqrt:Counter=~p, Total=~p.~n",[Final,Total+Final]),
    Total+Final;

% The Final value of Counter is a divisor of Number, but is not the exact square root; add both divisors to Total
% Note that we don't need to actually test that division, since it's the only remaining possibility.
sum_of_divisors(N,Final,Final,Total) when (N rem Final) =:= 0 ->
%    io:format("tail_eq:Counter=~p, Total=~p.~n",[Final,Total+Final+N div Final]),
    Total+Final+N div Final;

%Typical cases:

% '1' is always a divisor, so add it to the total    
sum_of_divisors(N,Final,Counter,Total) when Counter =:= 1 ->
%    io:format("typ_one:Counter=~p, Total=~p.~n",[Counter,Total+1]),
    sum_of_divisors(N,Final,Counter+1,Total+1);

% continue without adding to Total if Counter is not a divisor
sum_of_divisors(N,Final,Counter,Total) when (N rem Counter) =/= 0 ->
%    io:format("typ_neq:Counter=~p, Total=~p.~n",[Counter,Total]),
    sum_of_divisors(N,Final,Counter+1,Total);

% add the two divisors to the total if Counter is a divisor
sum_of_divisors(N,Final,Counter,Total) when (N rem Counter) =:= 0 ->
%    io:format("typ_eq:Counter=~p, Total=~p.~n",[Counter,Total+Counter+(N div Counter)]),
    sum_of_divisors(N,Final,Counter+1,Total+Counter+(N div Counter)).

tail.erl

-module tail.
-export [test/0].
-export [fib/1].

test() ->
    0 = tail:fib(1),
    1 = tail:fib(2),
    1 = tail:fib(3),
    2 = tail:fib(4),
    3 = tail:fib(5),
    5 = tail:fib(6),
    701408733 = tail:fib(45),
    ok.
    
% @doc fib calculates the Nth Fibonacci number using tail recursion
% There is no need for recursion to answer the first two cases, since they are defined to be zero and one.
fib(1) ->
    0;
fib(2) ->
    1;
fib(C) when C>2 ->
    % We start the call to fib/3 with the first two fibonacci numbers loaded
    fib(C,0,1).

%tail call
%We stop when the counter gets down to three, since we started with the first two fibonacci numbers already loaded
fib(3,I,A) ->
    A+I;

% C is the decrementing counter, I the intermediate (aka previous total) value, A the accumulated total
fib(C,I,A) ->
    fib(C-1,A,A+I).

I really wanted to replace the three separate tail calls with a single instance, using something like a Case statement to decide what to do between the three, but that seemed to be different than what is intended by the lesson.
Suggestions are welcome...

With a slight modification:

fib(0, I, _) ->
    I;
fib(C, I, A) ->
    fib(C-1, A, A+I);

The recursion works for fib(0) and fib(1) too, so there is no need to hard-code them in the trampoline function. In fact, the results are hard-coded in the first two extra values fib(C,0,1).

::raises grappa::
Thank you Matteo!