#include <stdio.h>

int factorial(int n);
void main()
{
    int n;
    printf("Enter your number : " );
    scanf("%d",&n);
    if(n <= 1)
    {
        printf("The factorial of the number n is ",n);
    }
    else
    {
        int res = factorial(n);
        printf("The result is %d\n",res);
    }
}
int factorial(int n)
{
    if(n <= 1)
        return 1;
    return n * factorial(n-1);
}

I'm doing a recursive function concept for the first time and i pretty much got like a 65% grasp on the concept of recursion. In the above program i have written a factorial recursion function and it goes normally well and i get the output but i'm trying to think where the recursion ends

Like for example i have gave an input of 5 :

The result is 120

but the main thing i wanted is why it doesn't continue after 0, if n <= 1(given if n = 0,-1...and so on during recursion) and then it should keep on returning "1" and multiplying with the recursion function(the factorial function being called inside the "factorial" function).In conclusion I really have no idea where the recursion ends...can you please clear it up.

CodePudding user response：

In conclusion I really have no idea where the recursion ends..

It ends at the return 1; statement:

int factorial(int n)
{
    if(n <= 1)
        return 1;  <---- Here
    return n * factorial(n-1);
}

Maybe it's more clear if you wrote it like:

int factorial(int n)
{
    if(n <= 1)
    {
        // No more recursive calls - just return 1
        return 1;
    }
    else
    {
        // Do recursive call with decremented argument
        return n * factorial(n-1);
    }
}

So the code keeps doing recursive calls until n becomes 1. Then it returns 1 to the previous recursive call which returns 2 (2 * 1) to the previous recursive call which returns 6 (3 * 2) to the previous recursive call which returns 24 (4 * 6) .... and so on.

So the final result is calculated like:

1 * 2 * 3 * 4 * ...
\---/   
  2   * 3
\-------/
    6     * 4
\-----------/
      24

CodePudding user response：

Lets say you have call factorial(3), then the call-chain will be something like this:

factorial(3)  // Initial call
    factorial(2);
        factorial(1);
            return 1;  // No more recursion
        return 2 * 1;  // 1 is the result of factorial(1)
    return 3 * 2;  // 2 is the result of factorial(2)

The result of factorial(3) will be 6 (3 * (2 * 1)).

CodePudding user response：

From Recursion:

In mathematics and computer science, a class of objects or methods exhibits recursive behavior when it can be defined by two properties:

• A simple base case (or cases) — a terminating scenario that does not use recursion to produce an answer.

• A recursive step — a set of rules that reduces all successive cases toward the base case.

So, terminating scenario('s)/condition('s) is one of property of recursion and it's where the recursion ends.

In context of your program:

Your program is finding the factorial of a given number n.

The factorial of a non-negative integer n is the product of all positive integers less than or equal to n:

n ! = n * ( n − 1 ) * ( n − 2 ) * ( n − 3 ) * ..... * 3 * 2 * 1

which is equivalent to

n ! = n * ( n - 1 ) !

that means, when writing program to calculate the factorial of a number n, we have to calculate the product of all positive integers and stop when reached to 1, which is the terminating condition.

In factorial() function:

int factorial(int n)
{
    if(n <= 1)
        return 1;
    return n * factorial(n-1);
}

The condition if(n <= 1) is the terminating condition for recursive function finding the factorial of n and its where the recursive function factorial() ends.

Additional:

• In your program, you are missing the format specifier in this printf() statement:

  printf("The factorial of the number n is ",n);

it should be

printf("The factorial of the number n is %d\n",n);
                                         ^^

• Note that, 0! is 1 and, after making above change, your program will give output as 0 when user give input number 0 which is wrong.

May you should write function to calculate factorial of given positive number n like this:

unsigned int factorial(unsigned int n) {
    if (n == 0) {
        return 1;
    } else {
        return n * factorial(n - 1);
    }
}

and add a check on user input before calling factorial(). This will take care of 0! as well.

• Using void as return type of main function is not as per standards. The return type of main function should be int.