Step 9 (S-4955)

From Stepik Wiki
Jump to: navigation, search

Step on Stepik: https://stepik.org/lesson/538/step/9

В коде программы определена следующая функция:


int foo(int n) {
    if (n <= 0)
        return 1;
    return foo((n * 2) / 3) + foo(n - 2);
}


Нужно посчитать, сколько всего раз будет вызвана функция foo, если ее вызвать с аргументом 3 (т.е. foo(3)). Самый первый вызов тоже нужно посчитать. 

Подсказка: для решения этой задачи будет полезно нарисовать дерево рекурсивных вызовов.