아래 코드의 함수중 sum2()는 제가 작성한 코드, sum()는 책에서 나오는 답안입니다. 제 생각으로는 sum2와 sum이 재귀호출되는 갯수는 같다고 생각해서 sum2로 제출을 했는데 시간초과가 떴습니다. sum()은 시간내에 통과를 했고요. 둘다 비슷한 시간이 걸릴거라고 생각했는데 시간이 이렇게나 차이가 나는 이유를 모르겠습니다. 제가 뭔가 잘못 생각한게 있는지 알고 싶습니다

#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

int cache[101][101];
int triangle[101][101];
int n;
int maxNum;

void init();
void sum2(int y, int x);
int sum(int y, int x);

int main(void)
{
    int testcase;
    cin >> testcase;
    while (testcase--)
    {
        init();
        cout << sum(0, 0) << endl;
        //sum2(0, 0);
        //cout << maxNum << endl;
    }
    return 0;
}

void init()
{
    int i,j;
    maxNum = 0;
    memset(cache, 0, sizeof(cache));
    cin >> n;
    for (i = 0; i < n; ++i)
    {
        for (j = 0; j <= i; ++j)
        {
            cin >> triangle[i][j];
        }
    }
    //cache[0][0] = triangle[0][0];
}

int sum(int y, int x)
{
    if (y == n - 1) return triangle[y][x];

    int& ret = cache[y][x];
    if (ret != 0) return ret;
    return ret = max(sum(y + 1, x), sum(y + 1, x + 1)) + triangle[y][x];
}

void sum2(int y, int x)
{   
    if(y == n-1) {
        maxNum = max(maxNum, cache[y][x]);
        return;
    }

    if (cache[y + 1][x] < cache[y][x] + triangle[y + 1][x])
    {
        cache[y + 1][x] = cache[y][x] + triangle[y+1][x];
    }
    cache[y + 1][x + 1] = cache[y][x] + triangle[y+1][x+1];
    
    sum2(y + 1, x);
    sum2(y + 1, x + 1);
}