Write a recursive method for sum of n integers?

Introduction

Recursion is a method calling itself. Such a method is said to be a recursive method. A recursive algorithm is similar to Mathematical Induction problems. We assume that there is a solution for a base case, and we will prove the result for the general case.

For example:

Sum(n) = 1 + 2 + 3 + …. + n-1 + n

A base case should be stated.

Sum(1) = 1

While coding recursive method we need to make sure that we end it successfully. The argument passed to the recursive method should converge to the base case. Each call will invoke a reduced problem so that it will reduce to the base case.

Sum(n) = n + Sum(n-1)

Sample infinite loop using recursion:

public class InfiniteRecursion {

public static void main(String[] args) {
 infinity();
 System.out.println("I'm in main method.!");
 }

public static void infinity(){
 infinity();
 }

}

 

Once the control is passed from main() to the infinity(), it will never return to the main(). infinity() method calls itself. The program falls in an infinite loop and leads to “StackOverflowError”. This is a common problem in recursive programs if we don’t converge to the base case.

 

Recursive program for Sum(n)

import java.util.Scanner;

public class RecursiveSum {
 
 public static void main(String[] args) {
 Scanner in = new Scanner(System.in);
 System.out.println("Enter n");
 int n = in.nextInt();
 System.out.println("Sum of n =" + n + " is:" + sum(n));
 in.close();
 } 
 
 public static int sum(int n){
 if(n==1) return 1;
 return n+ sum(n-1);
 }
}

 

Mathematical formula for sum:

sum(n) = ( n*n + n )/2 = n(n+1)/2