как посчитать количество итераций рекурсивной функции С++

Question

как посчитать количество итераций рекурсивной функции С++

Рейтинг: -1Ответов: 1Опубликовано: 27.04.2023

как посчитать кол-во итераций в рекурсивной функции без использования ссылок, указателей, областей видимости и вывести в консоль на примере кода снизу

(функция считает число Фибоначчи под номером N)

int FibRec(int N)
{ 
    if (N == 2)
        return 1;
    if (N == 1)
        return 1;
    return FibRec(N - 2) + FibRec(N - 1);
}

буду очень благодарен за помощь!

PS:

вот код всей программы

#include<iostream>
using namespace std;

int FibRec(int N)
{
    if (N == 2)
        return 1;
    if (N == 1)
        return 1;
    return FibRec(N - 2) + FibRec(N - 1);
}

int main()
{
    for (int i = 0; i < 5; i++) {
        int N;
        cout << "N" << i << " = ";
        cin >> N;
        cout << FibRec(N) << endl;
    }
    return 0;
}

цель программы посчитать 5 чисел Фибоначчи и узнать кол-во итераций затраченных на это

c# функции рекурсия

Источник: Stack Overflow на русском

Answer 1

▲ 0Принят

можно воспользоваться публичной переменной-счетчиком и внутри функции поставить инкремент чтобы при каждой итерации счетчик увеличивался на единицу

int counter = 0; // счетчик 
int FibRec(int N)
{
    counter++; //инкремент
    if (N == 2)
        return 1;
    if (N == 1)
        return 1;
    return FibRec(N - 2) + FibRec(N - 1);
}

таким образом при завершении функции мы получим переменную содержащую кол-во итерации затраченных на выполнение данной функции которую мы сможем использовать далее в коде

#include<iostream>
using namespace std;

int counter = 0;
int FibRec(int N)
{
    counter++;
    if (N == 2)
        return 1;
    if (N == 1)
        return 1;
    return FibRec(N - 2) + FibRec(N - 1);
}

int main()
{
    for (int i = 0; i < 5; i++) {
        int N;
        cout << "N" << i+1 << " = ";
        cin >> N;
        cout << FibRec(N) << endl;
    }
    cout << "how iter = " << counter << endl;
    return 0;
}

вывод:

N1 = 4
3
N2 = 5
5
N3 = 3
2
N4 = 4
3
N5 = 7
13
how iter = 47

как посчитать количество итераций рекурсивной функции С++

Ответы