factorial with Recursion in c++ language

factorial program in c++ language

The arrows into an activation bar indicates the argument passed by the caller; the arrows out show the value passed back to the caller. The length of a bar represents the time during which that invocation of the function is active 

n! = n ·(n−1)·(n−2)·(n−3)··· 2 · 1
#include <iostream>
/*
* factorial(n)
* Computes n!
* Returns the factorial of n.
*/
int factorial(int n) 
{
    if (n == 0)
       return 1;
    else
      return n * factorial(n - 1);
}
int main() 
{
    // Try out the factorial function
    std::cout << " 0! = " << factorial(0) << '\n';
    std::cout << " 1! = " << factorial(1) << '\n';
    std::cout << " 6! = " << factorial(6) << '\n';
    std::cout << "10! = " << factorial(10) << '\n';
}
recursion fuction in cpp language with example Androwep-Tutorials
recursion fuction in cpp language with example Androwep-Tutorials
factorial(6) = 6 * factorial(5)
= 6 * 5 * factorial(4)
= 6 * 5 * 4 * factorial(3)
= 6 * 5 * 4 * 3 * factorial(2)
= 6 * 5 * 4 * 3 * 2 * factorial(1)
= 6 * 5 * 4 * 3 * 2 * 1 * factorial(0)
= 6 * 5 * 4 * 3 * 2 * 1 * 1
= 6 * 5 * 4 * 3 * 2 * 1
= 6 * 5 * 4 * 3 * 2
= 6 * 5 * 4 * 6
= 6 * 5 * 24
= 6 * 120
= 720

Note that the factorial function can be slightly optimized by changing the if’s condition from (n == 0) to (n < 2). This change results in a function execution trace that eliminates two function calls at the end: 

factorial(6) = 6 * factorial(5)
= 6 * 5 * factorial(4)
= 6 * 5 * 4 * factorial(3)
= 6 * 5 * 4 * 3 * factorial(2)
= 6 * 5 * 4 * 3 * 2 * 1
= 6 * 5 * 4 * 3 * 2
= 6 * 5 * 4 * 6
= 6 * 5 * 24
= 6 * 120
= 720
#include <iostream>
/*
* factorial(n)
* Computes n!
* Returns the factorial of n.
*/
int factorial(int n) 
{
    int product = 1;
    for (int i = n; i > 0; i--)
        product *= i;
        return product;
}
int main() 
{
    // Try out the factorial function
    std::cout << " 0! = " << factorial(0) << '\n';
    std::cout << " 1! = " << factorial(1) << '\n';
    std::cout << " 6! = " << factorial(6) << '\n';
    std::cout << "10! = " << factorial(10) << '\n';
}

Note that this gcd function is recursive. The algorithm it uses is much different from our original iterative version. Because of the difference in the algorithms, this recursive version is actually much more efficient than our original iterative version. A recursive function, therefore, cannot be dismissed as inefficient just because it is recursive.

are the sum of their two immediately preceding elements; thus, the third number is 0 + 1 = 1, the fourth number is 1+1 = 2, the fifth number is 1+2 = 3, etc. The numbers that comprise the Fibonacci sequence are known as Fibonacci numbers. Note that 3 is a Fibonacci number but 4 is not. 

// Returns the nth Fibonacci number
int fibonacci(int n) {
if (n <= 0)
return 0;
else if (n == 1)
return 1;
else
return fibonacci(n - 2) + fibonacci(n - 1);
}

Each recursive invocation must bring the function’s execution closer to it base case. The factorial function calls itself in the else clause of the if/else statement.

Related Posts