Number of recursive function calls

Asked

Viewed 1,557 times

1

Hello. How could you know how many times a function is called recursively by its code?

For example, in the code below, how to know how many asterisks the function prints for a given value n?

int fibonacci(int n) {
    printf("*");
    if ((n == 1) || (n == 2))
        return (1);
    return (fibonacci(n-1) + fibonacci(n-2));
}
c recursion
  • 1

    It’s just having a variable that controls this, like everything you want a state, but it depends on how you want it to know how to do it. Anyway when it starts to have a lot of complication it is better not to do recursive.

  • A global variable does not help?

  • So I actually wanted a mathematical expression for that. For example, for n = 3 prints 3 asterisks, for n = 5 prints 9 f(3) = 3 f(5) = 9 I don’t want the program to do that. I want a way to understand how to calculate this number.

  • 1

    Are you interested in the complexity of your algorithm? If it is interesting to include this in your question...

  • Yeah, I think that’s what I want.

  • If to use a global variable it makes no sense to do something recursive.

  • 2

    Possible duplicate of How to optimize this function for Fibonacci sequence?

  • Although the question I marked as duplicate is Javascript instead of C, the code there has the same functioning and the answers there should serve to answer your question.

  • Let me ask: do you want to know this for any function? For example, "I want to know how often my function int quadrado (int n) was called"? If so, I believe you could use more professional tools such as the GCOV.

  • Actually this is an exercise, a question was given: "In the program below, how many times * is printed for an input n?"

Show 5 more comments

2 answers

1

it’s easy, you can create a variable to count it:

int qtd = 0;

int fibonacci(int n) {
    qtd += 1;
    printf("chamado: %d \n", qtd);
    if ((n == 1) || (n == 2))
        return (1);
    return (fibonacci(n-1) + fibonacci(n-2));
}

Tested on the website online_c_compiler

  • This code counts how many times the function is called and not how many times it is recursively called. For example, with n=3 function will make 2 recursive calls, fibonacci(3-1) and fibonacci(3-2).

  • @Jorge B. just decrease the counter before printing...

0

I think you can put the second Return inside an 'Else' and so add the counting variable

int qtd = 0, aux = 0;

int fibonacci(int n) {
    printf("*");
    if ((n == 1) || (n == 2)){
        return (1);
    qtd = aux ; /*Recebe o número de chamadas recursivas, vc decide como usar essa 
    variável no resto do código rsrsrs, é essa variável que vai conter o valor que 
    você quer*/ 

    aux = 0; //Zerei a variável para o caso de vc chamar a função de novo

}
    else{
    return (fibonacci(n-1) + fibonacci(n-2));
    aux++;
    }
}

Browser other questions tagged c recursion

You are not signed in. Login or sign up in order to post.