In this article, we are going to have a look at SUM OF THE NATURAL NUMBERS USING RECURSION and FACTORIAL USING RECURSION.
INTRODUCTION: SUM OF THE NATURAL NUMBERS USING RECURSION
In this tutorial, we are going to learn about the sum of the first n natural numbers using recursion.
For example:
Input n: 5
Output: 1+2+3+4+5 = 15.
APPROACH 1
we can find sum fo the natural numbers recursively. Until the value of the number is greater than zero, the recursive function will call itself. In this manner, the sum of n natural numbers is calculated.
ALGORITHM
Step 1: Start.
Step 2: recursive function will call itself until the value is greater than zero.
Step 3: until the value is greater than zero, store the value by using the above formula.
If n >0 return return n+(n-1).
else return n.
Step 4: Stop.C++ Code:
#include <iostream>
using namespace std;
int SumRec(int n){
if (n>0) return n+SumRec(n-1);
else return n;
}
int main() {
int n;
cin>>n;
cout<<"SUM OF FIRST "<<n<<" NUMBERS IS : "<<SumRec(n);
}
Python code:
def SumRec(n):
if n>0 :
return n+SumRec(n-1)
else :
return n
n = int(input())
print("SUM OF FIRST",n,"NUMBERS IS :",SumRec(n))
JAVA code:
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner s = new Scanner(System.in);
int n = s.nextInt();
Sum sum = new Sum();
System.out.println("SUM OF FIRST "+n+" NUMBERS IS : "+sum.SumRec(n));
}
}
class Sum{
public int SumRec(int n){
if(n>0) return n+SumRec(n-1);
else return n;
}
}
Input: 10
Output: SUM OF FIRST 10 NUMBERS IS : 55
The time complexity of the code is O(n).
The space complexity of the code is O(n), as we use a stack for storing each recursive call.INTRODUCTION: FACTORIAL USING RECURSION
In this tutorial, we are going to calculate the factorial of a number using recursion.
First of all, what is meant by the factorial of a number?
The Factorial of a non-negative number is the multiplication of all the numbers that are less than or equal to the particular number.
The Factorial of a number is represented by an exclamatory symbol (!).
For example:
6!, 5!, 10!. these are representations of the factorial of the respective numbers.
Let’s take an example of the mathematical calculation of the factorial of a number.
Ex1:
5! = 5*4*3*2*1 = 120. the value of 5! is 120.
APPROACH 1
we can find the factorial of a number recursively. Until the value of the number is equal to 0 or 1, the recursive function will call itself. In this manner, the factorial of a number is calculated.
ALGORITHM
Step 1: Start.
Step 2: recursive function will call itself until the value is greater than or equal to zero.
Step 3: until the value is greater than or equal to zero, store the value by using the above formula.
If n == 0 or n == 1 return 1
else return n*(n-1)!
Step 4: Stop.C++ Code:
#include <iostream>
using namespace std;
int factorial(int n){
if( n == 1 || n == 0) return 1;
else return n*factorial(n-1);
}
int main() {
int n;
cin>>n;
cout<<"FACTORIAL IS : "<<factorial(n);
}
Python code:
def factorial(n):
if n == 0 or n == 1:
return 1
else:
return n*factorial(n-1)
n = int(input())
print("FACTORIAL IS :",factorial(n))
JAVA code:
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner s = new Scanner(System.in);
Factorial f = new Factorial();
int n = s.nextInt();
System.out.println("FACTORIAL IS : "+f.factorial(n));
}
}
class Factorial {
int factorial(int n){
if( n == 1 || n == 0) return 1;
else return n*factorial(n-1);
}
}
Input: 5
Output: FACTORIAL IS : 120
The time complexity of the code is O(n).
The space complexity of the code is O(n), as we use a stack for storing each recursive call.
CONCLUSION
That’s it from this tutorial. Hope you guys found It interesting. We have solved the sum of n natural numbers and the factorial of a number using recursion in different programming languages. Happy coding!