SUM OF THE NATURAL NUMBERS USING RECURSION and FACTORIAL USING RECURSION

SUM OF THE NATURAL NUMBERS USING RECURSION and FACTORIAL USING RECURSION

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.

See also  SELECTION SORT ALGORITHM

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!

Leave a Comment

Your email address will not be published. Required fields are marked *