Exploring Tail Recursion

Here is a math puzzle that is explored in this post:
Find the smallest positive integer n such that n % x = x-1 for x from 2 to 18
i.e. The remainder is one less than the divisor for all integral divisors from 2 to 18.

The solution is tail recursive, but alas, Java and Ruby 1.8 (and C#) don't optimize tail calls, so they overflow. Erlang handles it.

I discovered this the hard way and so I had switch to iteration in Ruby and Java. I am not 100% sure if my Erlang solution is indeed tail recursive (the if statement ends after the last function call) but it does run noticeably faster than the others. I am a novice Ruby and Erlang coder, all code improvement suggestions will be gratefully accepted (expect for ones that call out for hard coding/error handling/better names, this is a puzzle dammit.)

public class Eighteen{
public static void main(String[] args){
System.out.println("answer is "+ new Eighteen().findit(1));
}

private int findit(int multiple){
int n = 180 * multiple - 1;
for(int divisor=17; divisor > 2; divisor--){
if (n % divisor != (divisor-1)) break;
if (divisor == 3) return n;
}
return findit(multiple+1);
}
}


def findit
i = 0
while i = i + 1
n = 180 * i - 1
17.downto 3 do |divisor|
if (n % divisor != (divisor-1))
break
end
if (divisor == 3)
puts "answer is #{n}"
exit
end
end
end
end


% Erlang solution

-module(find18).
-export([findit/0]).

is18(Num) -> is18(Num, 18).

is18(Num, 1) -> true;
is18(Num, Divisor) ->
(Num rem Divisor == (Divisor - 1)) andalso is18(Num, Divisor - 1).

findit() -> findit(1).

findit(Mult) ->
Candidate = 180 * Mult - 1,
Found = is18(Candidate),
if
Found -> Candidate;
true -> findit(Mult+1)
end.

6 comments:

Manoj said...

seems you should have written divisor > 2 in the for loop instead of divisor < 2

Sriram said...

@ Manoj
Thanks.

drcabana said...

Sriram, I posted what I think is a slightly more idiomatic erlang solution, along with some comments, on my blog, at http://erl.nfshost.com/2009/05/10/245245/

drcabana said...

I'm not sure why, but the link above did not paste properly. The final 245245 should just be 245. I'll try pasting it again and hope for the best.

http://erl.nfshost.com/2009/05/10/245/

Sriram said...

My colleague Ramesh Rajamani came up with this little gem of a solution in Erlang.

-module (math2).
-export ([findNum/2]).

findNum(N,1) -> N;
findNum(N,D) ->
if N rem D == D-1 ->
findNum(N,D-1);
true ->
findNum(N+1, 18)
end

Saager Mhatre said...

I know I'm a little late to the game, but I'd like to offer my solution to the mix.

Post a Comment