Created
May 14, 2020 02:14
-
-
Save EarlOfBDE/3e9108890c3b1fd11dac4e38bddc727d to your computer and use it in GitHub Desktop.
Tail Recursion chapter 2.5
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
-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)). |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
-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). |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
::raises grappa::
Thank you Matteo!