#include <stdio.h>

// recの呼び出し回数
int c = 0;

// a[n] = 2a[n-1] + a[n-2]
// a[1] = 2, a[2] = 3
int rec(int n)
{
    c++;

    if (n == 1)
    {
        return 2;
    }
    else if (n == 2)
    {
        return 3;
    }
    else
    {
        return 2 * rec(n-1) + rec(n-2);
    }
}

int main(void)
{
    int n = 4;
    int a;

    a = rec(n);

    printf("数列a%dの値は%d\n", n, a);
    printf("このときrecの呼び出し回数は%d\n", c);

    return 0;
}