Trying to find a recursive solution.

Question

Problem statement: Find the number of trailing zeros in the decimal representation of N!.

You can find the actual problem statement here.

Here is what I tried :

       #include <stdio.h>
       int fct(int n);
       int main(void)
        {

          int n,t;
          scanf("%d",&t);
          while(t-- > 0) 
          {
           scanf("%d",&n);
           printf("%d\n",fct(n)-n);
          }
          return 0;
         }
        int fct(int n)
        {
          static int s=0;
           if(n<5)
            return s+n;
           else
          {
           s=fct(n/5);
           s=s+n;
           return s;
          }
       }  

Any help would be appreciated.

P.S. My above recursive function does'nt return the actual answer and I was not able write a function that returns the actual answer(number of trailing zeroes). Hence I needed some help in doing so. I think the program I posted below does that.

Answer 1

   #include <stdio.h>
   int fct(int n);

That should be "static int fct(int n)". The static represents that the name fct has file scope, rather than the scope of the entire linked project.

   int main(void)
    {
     int n,t;
      scanf("%d",&t);
      while(t-- > 0) 

Don't mix persistent and functional behavior, even though C lets you. I suggest:

      int t;
      for (scanf("%d", &t); t > 0; t--) {

because it is a lot less confusing.

      {
       scanf("%d",&n);
       printf("%d\n",fct(n)-n);

Why are you calculating Z(n) + n? Why not just calculate Z(n) directly? Are you trying to make this hard on yourself?

      }
      return 0;
    }

    int fct(int n)

Don't name things fct. The english language has a lot of words in it. Learn to use them. Also, this function should be tagged as static to indicate that it has file scope rather than global scope.

    {
      static int s=0;

Don't make local variables static. It puts them in "static memory" rather than making a new variable on the stack, making your function only work once, then fail forever more.

       if(n<5) return s+n;
       else {
         s=fct(n/5);
         s=s+n;
         return s;
       }
   }  

Again, why this misery of trying to calculate Z(n) + n rather than just Z(n) ?

It appears what you are trying to implement tail recursion. Tail recursion is a type of recursion where the return value is passed on the stack as a parameter. You are avoiding the stack by using a static variable, which breaks everything, but effecting you are creating a helper function like:

int Z(n) {
  return Z2(n, 0);
}

int Z2(n, s) {
  if (...) {
    return s;
  }
  else {
    return ...Z(...n..., ...s...);
  }
}

Trying to learn tail recursion before you can do regular recursion is a bad idea. Just write it like:

int Z(n) {
  if (...) {
    return ...;
  }
  else {
    return ...Z(...n...)...;
  }
}

That said, since you are trying to implement it recursively, rather than as effeciently as possible, try to implement this:

   Sum = 0
   For each value from 1..n divisible by 5, add 1 to sum
   For each value from 1..n divisible by 25, add 1 to sum
   For each value from 1..n divisible by 125, add 1 to sum
   For each value from 1..n divisible by 625, add 1 to sum
   etc
   return sum

Try to implement that by starting by checking n, then recurring on Z(n - 1).

Answer 2

Thanks DanielIV for breaking the problem down.

Here is my working recursive solution which got accepted in SPOJ.

       #include <stdio.h>
       int factorial(int n);

       int main(void)
     {

       int t,n;

       for(scanf("%d",&t);t > 0;--t ) {
       scanf("%d",&n);
       printf("%d\n",factorial(n));
       }
       return 0;
     }

   int factorial(int n)
   {
   if(n<1)
   return 0;
   return (n/5 + factorial(n/5));
   }