CODEWITHSUNDEEP
crecursionprintffunction-call
Gilfoyle
Gilfoyle

Reputation: 3616

How to implement a running variable in a recursive function

At the moment I am coding a program in which I need a variable count that increments every time I call the function. In my case I have a recursive function and want to know how many iterations the program does.

I simplified the code by computing the factorial of a number.

My first approach does not work and ends up with warning messages:

#include <stdio.h>

int factorial(unsigned int i, int *count)
{
   *count += 1;
   if(i <= 1)
   {
     return 1;
   }
   return i * factorial(i - 1, &count);
}  

int  main()
{
   int i = 10;
   int count = 0;
   printf("%d Iterations, Factorial of %d is %d\n", count, i, factorial(i, &count));
   return 0;
}


warning: passing argument 2 of ‘factorial’ from incompatible pointer type

My second approach does not work either but also does not ends up with any warning messages.

#include <stdio.h>

int factorial(unsigned int i, int count)
{
   count += 1;
   if(i <= 1)
   {
     return 1;
   }
   return i * factorial(i - 1, count);
}   

int  main()
{
   int i = 10;
   int count = 0;
   printf("%d Iterations, Factorial of %d is %d\n", count, i, factorial(i, count));
   return 0;
}

How can I make it run? Any ideas? I use Ubuntu and gcc.

Upvotes: 0

Views: 1320

Answers (4)

Paul Ogilvie
Paul Ogilvie

Reputation: 25286

There is no need for static variables, as other solutions suggest. The following is correct:

int factorial(unsigned int i, int *count)
{
   *count += 1;
   if(i <= 1)
   {
     return 1;
   }
   return i * factorial(i - 1, count);
}   

int main(void)
{
   int i = 10;
   int count = 0;
   printf("%d Iterations, Factorial of %d is %d\n", count, i, factorial(i, &count));
   return 0;
}

One note: as the order of parameter evaluation in the printf statement is not guaranteed, as I understand it the value of count in the call to printf may either be zero (it is passed before factorial was called) or may be 10 (the value after factorial was called). Therefore, main could better be written as:

int main(void)
{
   int i = 10;
   int count = 0;
   int fact= factorial(i, &count);
   printf("%d Iterations, Factorial of %d is %d\n", count, i, fact);
   return 0;
}

6.5.2.2 Function calls: 10 The order of evaluation of the function designator, the actual arguments, and subexpressions within the actual arguments is unspecified, but there is a sequence point before the actual call.

Upvotes: 1

Rishikesh Raje
Rishikesh Raje

Reputation: 8614

There are two ways of solving this problem.

  1. Declare a static variable in the recursive function to count the no of times it is called.

e.g. 

int factorial(unsigned int i, int *count)
{
   static int count2;
   *count = ++count2;
   if(i <= 1)
   {
     return 1;
   }
   return i * factorial(i - 1, count);
}

int  main()
{
   int i = 10;
   int count = 0, fact;
   fact = factorial(i, &count);
   printf("%d Iterations, Factorial of %d is %d\n", count, i, fact);
   return 0;
}
  1. Have count as a pointer to integer, which can then be updated in each function to find the number of iterations.

e.g. 

int factorial(unsigned int i, int *count)
{
   (*count)++;
   // Remaining lines the same as first solution.
}

The second solution will only work in some special types of recursive functions where the first function calls the second and the second calls the third, etc. It will not work for example in a recursive fibbonaci sequence algorithm.

The first solution is a more general one, and will work for all conditions.

Upvotes: 0

ViKiG
ViKiG

Reputation: 783

Declare the count variable as static inside the factorial function itself. 

    static int count = 0;

Upvotes: 0

Sourav Ghosh
Sourav Ghosh

Reputation: 134286

In your first case, factorial() function, count is of type int *. So, while calling the function recursively (in the return statement), do not pass address of count, just pass the count itself.

That said, as count is to be modified in the function call of factorial(), don't pass both of them (the variable and the function call which modifies the variable) in the same argument list as there is no sequence point in the elements passed as argument list, so you'll end up invoking undefined behavior.

Upvotes: 0

Related Questions