Итеративный подход кажется медленнее, чем рекурсивная реализация (смена монет)

Проблема от ува О.Ю.

мое решение с рекурсией

#include <cstdio>using namespace std;

#define garbaze 0
//number of ways changes can be made
int coins[] = {garbaze,50,25,10,5,1}; //order does not matter//as         in         the     //count_ways... function we are returning
//0 if which_coin_now is <= 0 so it
//does n't matter what we have in the index 0 [garbaze] .. but we must put //something there to implement the
//code using the pseudo code or recursive relation
typedef unsigned long long ull; //simple typedef
ull dp[7490][6]; //2d table
//recursive approachull count_ways_of_changes(int money_now,int which_coin_now)
{
if(money_now == 0)
return 1;
if(money_now < 0 || which_coin_now <=0 )
return 0;
if(dp[money_now][which_coin_now] == -1)
dp[money_now][which_coin_now] = count_ways_of_changes(money_now,which_coin_now-1) //excluding current coin
+ count_ways_of_changes(money_now - coins[which_coin_now],which_coin_now) ; //including current coinreturn dp[money_now][which_coin_now] ;}

int main()
{
for(int loop = 0; loop< 7490 ;loop++)
for(int sec_loop = 0;sec_loop<6;sec_loop++)
dp[loop][sec_loop] = -1; //table initialization
int N = 0;
while(scanf("%d",&N)==1)
{
printf("%llu\n",count_ways_of_changes(N,5)); //llu for unsigned long long
}
return 0;
}

Этот был принят (и занял 0,024 с)

И мой итеративный подход:

#include <cstdio>
//#include <iostream>
//using namespace std;
typedef unsigned long long ull;
ull dp[7490][6];
#define garbaze 0
int value_coins[] = {garbaze,5,1,10,25,50} ;
inline ull count_ways_change(int money,int num_of_coins)
{
for(int sum_money_now = 0; sum_money_now <= money ;sum_money_now++)
for(int recent_coin_index = 0 ; recent_coin_index <= num_of_coins ; recent_coin_index++)
//common mistakes : starting the second index at num_of_coins and decrementing till 0 ...see we are pre calculating
//we have to start bottom to up....if we start at dp[0][5] .....to dp[1][5] but to know that i need to know
//dp[1][4] and dp[..][5] before hand ..but we have not calculated dp[1][4] yet...in this case i don't go to infinite
//loop or anything as the loop is well defined but i get stupid garbaze answer

{
if(sum_money_now == 0)
dp[sum_money_now][recent_coin_index] = 1;
else if(recent_coin_index == 0)
dp[sum_money_now][recent_coin_index] = 0;
else if(sum_money_now < value_coins[recent_coin_index] && recent_coin_index != 0)
dp[sum_money_now][recent_coin_index] = dp[sum_money_now][recent_coin_index-1] ;
else
dp[sum_money_now][recent_coin_index] = dp[sum_money_now][recent_coin_index-1] + dp[sum_money_now - value_coins[recent_coin_index] ][recent_coin_index] ;
//   cout<<dp[sum_money_now][recent_coin_index]<<endl;
}return dp[money][num_of_coins] ;
}
int main()
{/*
for(int loop = 0; loop< 7490 ;loop++)
for(int sec_loop = 0;sec_loop<6;sec_loop++)
dp[loop][sec_loop] = -1; //table initialization

*/ //In the iterative version do not need to initialize the table as we are working bottom - up
int N = 0;
while(scanf("%d",&N)==1)
{

printf("%llu\n",count_ways_change(N,5)); //llu for unsigned long long

}
return 0;
}

Но у меня превышено ограничение по времени для этого. Это дает правильный вывод, но я не вижу причины, почему этот должен быть таким медленным?