WAP to Calculate Factorial of a given Number using Recursion.
Objective
Write a C++ program to calculate a factorial using Recursion.
Algorithm / Approach
- Define a function
int fact(int x). - Establish a Base Case:
if (x == 0 || x == 1) return 1. - Establish the Recursive Step:
return x * fact(x - 1). - Call the function from
main().
main.cpp
#include<iostream>
using namespace std;
int fact(int);
int main(){
int n,res;
cout<<"Enter number: ";
cin>>n;
res = fact(n);
cout<<"Factorial : "<< res;
return 0;
}
int fact(int x){
if(x==0 || x==1){
return 1;
}
else{
return x*fact(x-1);
}
}Expected Output
Enter a Number : 5 Factorial = 120
Explanation of the Program
- Recursion is when a function calls itself to solve a smaller piece of the same problem.
- Every recursive function MUST have a "Base Case" (a condition where it stops calling itself). Without a base case, the function will call itself infinitely until the computer crashes with a "Stack Overflow" error.
Complexity
Time Complexity
O(n)
Space Complexity
O(n) - Due to the call stack memory used by recursion.
