I asked the problem of the tribonacci sequence in C ++ & the number of function calls when writing with the recurrence function (python is also available)

Introduction

This is my first article. I found an article that looked interesting, so I tried it. I tried to solve the tribonacci sequence problem with Ruby (time limit 10 minutes) Pioneer -I tried to solve the tribonacci sequence problem with Elixir (time limit 10 minutes) -I tried to solve the tribonacci sequence problem in Ruby, with recursion.

What i did

・ 10 minutes challenge in C ++ (failed because the calculation time is too long) ・ 30 minutes challenge (clear) in C ++ -About the number of function calls when writing recursively (python implementation included)

10 minutes challenge in C ++ (failure)

First of all, I came up with a method to do it recursively and wrote it as it is. The point is to find the 50th of the tribonacci sequence in the first term [1,3,7].

tribonacci_recursive.cpp

#include <iostream>
#include <chrono>
using namespace std;

long long tri_r(int num){
    if(num<=3){
        int templist[3] = {1,3,7};
        return templist[num-1];
    }
    else{
        return tri_r(num-1)+tri_r(num-2)+tri_r(num-3);
    }
}

int main(){
    chrono::system_clock::time_point  start, end;
    start = std::chrono::system_clock::now();
    cout << tri_r(51) << endl;
    end = std::chrono::system_clock::now();
    double e_time = std::chrono::duration_cast<std::chrono::milliseconds>(end-start).count();
    cout << e_time << " ms" << endl;
}

Yes, this doesn't finish the calculation in Matomo time. That's why I rewrote it so that I don't have to do unnecessary calculations. At this point, 10 minutes had passed, so the challenge failed.

30 minutes challenge (clear) in C ++

tribonacci.cpp

long long tri(int num){
    if(num<3){
        int templist[3] = {1,3,7};
        return templist[num-1];
    }
    else{
        long long tri_list[num] = {1,3,7};
        for(int i=3; i<num; i++){
            tri_list[i] = tri_list[i-1] + tri_list[i-2] + tri_list[i-3];
        }
        return tri_list[num-1];
    }
}
int main(){
    chrono::system_clock::time_point  start, end;
    start = std::chrono::system_clock::now();
    for(int i=1; i<51; i++){
        cout << i << "  " << tri(i) << endl;
    }
    end = std::chrono::system_clock::now();
    double e_time = std::chrono::duration_cast<std::chrono::milliseconds>(end-start).count();
    cout << e_time << " ms" << endl;
}

The processing when it is 3 or less is not good, but it can be calculated in an instant. The code outputs from tri (1) to tri (50), but it is still 20 ms. It will be enough.

Number of function calls when written recursively

By the way, when I wrote it in recursion, I understand that it is doing useless calculations, but how does the number of calls to this function increase?

You can see it. The number of calls is calculated by the tribonacci sequence of the first term {1,1,1}. It's natural when you think about it, but it's a nice fact.

I tried to measure the calculation time by recursion. Pick up only where it ends with a matomo calculation time (measured 10 times and averaged).

In items 34 to 36, the calculation time is about 1.85 times and 1.87 times, respectively. How about the number of calls? I wrote it in Python, which I'm used to.

tri_calc.py

def tri(num):
    ans_list = [1,1,1]
    if num > 3:
        for i in range(3, num):
            ans_list.append(ans_list[i-3] + ans_list[i-2] + ans_list[i-1])
    return ans_list

calc_num = tri(50)
print(calc_num[35]/calc_num[34])  #1.8392867552142929
print(calc_num[36]/calc_num[35])  #1.8392867552141035

So, you can see that the number of function calls is about 1.84 times each time one term is added. The increase in calculation time is mostly like call overhead.

in conclusion

It was my first post, and it was in Markdown or Nanisore state. Please let me know if you find it easier to read if you write it like this. I'm still a beginner in programming and coding, but it's fun to solve these problems and verify them in various ways. Thank you for reading.