Consider a simple recursive method (Java code written by yourself or taken from
ID: 3873279 • Letter: C
Question
Consider a simple recursive method (Java code written by yourself or taken from Web) such as calculating the sum of the first n natural numbers, calculating the number of digits of an integer number, calculating 2 to the power of n, etc. Try choosing one different from that of any posted thus far. a. Show method code, indicate what it does, identify the base case(s) and indicate how each recursive call simplifies the problem and makes progress towards the base case; b. Provide an equivalent iterative implementation. c. How do the two implementations compare?
Explanation / Answer
Checking if a number is prime or not:
Java code:
-------------------------------------------------------------------------------------------------------------------------------------------------
import java.util.Scanner;
public class PrimeNumber
{
public static void main(String[] args)
{
int n, output;
Scanner s = new Scanner(System.in);
System.out.print("Enter any number:");
n = s.nextInt();
PrimeNumber obj = new PrimeNumber();
output = obj.checkIfPrime(n, 2);
if(output == 1)
{
System.out.println(n+" is prime number");
}
else
{
System.out.println(n+" is not prime number");
}
}
int checkIfPrime(int number,int counter)
{
if(counter < number)
{
if(number % counter != 0)
{
return(checkIfPrime(number, ++counter));
}
else
{
return 0;
}
}
return 1;
}
}
---------------------------------------------------------------------------------------------------------------------------------------------------
As you can see in above code, "checkIfPrime" is a recursive function. It recursively calls itself until the dividend is smaller than or equal to divisor.The base case is when input number is "2". In the method "checkIfPrime", it will return false in the very first call from the condition "2<2".
For any number N to be a prime number, it must not be divisible by any other number than 1 and itself. So with each recursive call, we are checking if is divisible by (2 + i), where i increase by one from 1 to N consecutively with each call. At any point, if the condition of being not divisible by any other number is violated,the function call returns false and exit the recursive loop consecutively and gives a false when control goes back to main function.
----------------------------------------------------------------------------------------------------------------------------------------------
C code for equivalent function:
int checkIfPrime(int n){
int i = 2, result;
do{
result = n%i;
if(result == 0) break;
i++;
}while(n != i);
if(n == i) return 1;
else return 0;
}
---------------------------------------------------------------------------------------------------------------------------------
Above mention code is a C equivalent of recursion to find prime number. It is checking wheteher a number N is prime or not by using iterative approach. It checks for 1,2,3....N-1 to be able to perfectly divide N. If the validation fails at any point it returns "0",equivalent of false, to the main().
In recursion, function is calling itself repeatedly to check for a prime number while in iterative approach, a part of the code is repeatedly executed for new values. Recursion is easy to follow for any developer than Iteration. It requires lesser lines of code and also lesser variables in most of the cases.