Nie popełniasz błędu merytorycznego, w istocie, ale twój algorytm jest zbyt wolny, poza tym nie jestem pewien, czy przypadkiem nie wykracza poza zakres zmiennych dla danych w zadaniu.
Dwa słowa: arytmetyka modularna.
A co do różnicy między algorytmem rekurencyjnym a iteracyjnym, to raczej szybkość jest ta sama, jeśli algorytm jest dokładnie ten sam, rekurencja co najwyżej może przepełnić stos.
Poza tym: http://pl.spoj.com/forum-old/viewtopic.php?f=1&t=222
