CODEWITHSUNDEEP
c
Xuer
Xuer

Reputation: 83

tried a example from a c tutorial site kinda got it wrong

I was learning about recursion in C from https://www.tutorialspoint.com/cprogramming/c_recursion.htm and I tried the number factorial example.

#include <stdio.h>

int fact(int i) {
    if (i <= 1) {
        return 1;
    }
    return fact(i - 1);
}

int main() {
    int i = 3;
    printf("numb = %d", fact(i));
    return 0;
}

After I executed the code it printed 1. I reviewed the code and found that I forgot to multiply var i with fact(i - 1) at the end of the function. I fixed it and got the correct factorial, but why is fact(3 - 1) equal to 1?

Edit

I had a very shallow understanding of recursion when i posted this question,i thought fact(i-1) would just execute once and didn't get the meaning of calling the function again in the tutorial and i didn't understand it at first when i read the busybee's answer i think i get it now fact(3-1) called fact(2-1) value of var i is now 1 and it satisfied the if condition and returned 1. Another question in the correct version where i multiply var i with fact(i-1) when i change return 1 to return 2 why does it return 12, from the pattern of return 1 and return 2 it seem to multiply 6 result of the function fact with the number in return why? i admit i did no research on what return does and just kinda went with the flow.

Upvotes: 0

Views: 100

Answers (2)

the busybee
the busybee

Reputation: 12653

fact(3 - 1) returns 1 in your first and erroneous version, because it called fact() with i with 2.

This is not less or equal to 1, so fact() is called with 2 - 1. Now this is less or equal to 1, and 1 is returned.

This result is unchanged returned again, and finally once more returned to main().

As a list:

  • main() calls fact(3).
    • fact(3) calls fact(2), because its i is 3 and so greater than 1.
      • fact(2) calls fact(1), because its i is 2 and so greater than 1.
        • fact(1) returns 1 to fact(2), because its i is less or equal to 1.
      • fact(2) returns the 1 returned from fact(1) unchanged to fact(3).
    • fact(3) returns the 1 returned from fact(2) unchanged to main().
  • main() prints the 1 returned from fact(3).

Edit:

When you're in doubt how your functions are called and what they do, use a debugger (best approach) or insert some printf() (poor man's debugging, but quite easy), like this:

int fact(int i) {
    printf("fact(%d) begins ...\n", i);
    if (i <= 1) {
        printf("... fact(%d) returns 1 because of %d <= 1\n", i, i);
        return 1;
    }
#if 1 // just temporarily
    printf("... fact(%d) calls fact(%d)\n", i, i - 1);
    int r = fact(i - 1);
    printf("... fact(%d) returns %d\n", i, r);
    return r;
#else
    return fact(i - 1);
#endif
}

Edit 2:

You might have missed some important things in the lesson on recursive functions.

  • Each function has its own set of parameters and local variables.
  • In general, a recursively called function does not have any insight in the local variables or parameters of the calling function.
  • A recursively called function returns to the calling function. (Some compilers might optimize a "tail call" into a "tail jump", though.)

Upvotes: 0

MED LDN
MED LDN

Reputation: 669

To compute the factorial recursively, i must be a positive integer. So that either the value of i is 0 or 1 the factorial will be 1.

If not, then call the recursive factorial algorithm with (i - 1) then multiply the result by i and return that value as shown:

#include <stdio.h>

int fact(int i)
{
   if (i ==1)
      return 1;

   return fact(i - 1) * i; // You forgot to multiply  i  here
}

int main(void)
{
    int i = 3;
    printf("Number = %d", fact(i)); // Displaying the factorial of 3

    return 0;
}

Upvotes: 3

Related Questions