How many recursive calls

hopesfall (179)
How would I know how many recursive calls were needed to solve a given base and exponent in the following program? Could I just add a "counter++" inside the powers function and get the correct answer by looking at what counter ends up being? This is what I tried:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
 

#include <iostream>
double powers(double baseNumber, unsigned int exponentNumber)
{
    counter++

    if (exponentNumber == 0)
        return 1;

    double sq = powers(baseNumber, exponentNumber/2);
    sq *= sq;

    if (exponentNumber % 2 == 0 )
        return sq;
    else
        return baseNumber * sq; 
}
int main()
{
    double base = 3.0;
    unsigned int exponent = 2;
    std::cout << powers(base, exponent) << '\n';
    std::cout << powers(10, 100) << '\n';
    std::cout << powers(2, 100) << '\n';
}

Last edited on
Moschops (7244)
There are various solutions. Here is one:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
 
#include <iostream>
double powers(double baseNumber, unsigned int exponentNumber, int& counter)
{
   counter++;

    if (exponentNumber == 0)
        return 1;

    double sq = powers(baseNumber, exponentNumber/2, counter);
    sq *= sq;

    if (exponentNumber % 2 == 0 )
        return sq;
    else
        return baseNumber * sq; 
}
int main()
{
    int counter = 0;
    double base = 3.0;
    unsigned int exponent = 2;
    std::cout << powers(base, exponent, counter) << " " << counter << '\n';
    counter = 0;
    std::cout << powers(10, 100, counter) << " " << counter << '\n';
    counter = 0;
    std::cout << powers(2, 100,counter) <<  " " << counter << '\n';
}

Last edited on
hopesfall (179)
Wouldn't that give me one more than what is really true? I say this because counter gets incremented immediately when entering the function, should it be counted the very first time we enter the function, even though we haven't recursively called anything yet?
Moschops (7244)
Are you trying to count how many times the function powers is called, or how many times it calls itself (which will be how many times it is called, minus one)?
Topic archived. No new replies allowed.