D.4.02 Describe the application of recursive algorithms.
Application of recursive algorithms
In mathematics and computer science, a class of objects or methods exhibit recursive behavior when they can be defined by two properties: (wikipedia)
A simple base case (or cases) - to be used as a stopping state
A set of rules that reduces all other cases toward the base case
Therefore, a method is said to be recursive if it calls itself, has simple base case/s, and has a set of rules to reduce all the other cases toward the base case.
Recursion explained in actual code (Java)...
For instance, if you're asked to find the sum of numbers from 1 to n, you can think of the process like this: You start with 1, add 2, then 3, and so forth until you reach n.
sum(n) = 1 + 2 + 3 + . . . + n, where n >= 1
Java's looping constructs make implementing this process easy. But you may look at the same problem differently:
sum(n) = 1 //set as the base case
sum(n) = n + sum(n - 1) if n > 1
From the above illustration, let's consider the definition by calculating the sum(4)
sum(4) = 4 + sum(3)
= 4 + 3 + sum(2)
= 4 + 3 + 2 + sum(1)
= 4 + 3 + 2 + 1
And because sum(1) is set as our base case without referring to further invocations, this saves the process from going on forever.
IMPLEMENTING RECURSION:
Example 1:
private static long factorial(int n){ //creates a factorial method with int parameter
if (n == 1) //sets the base case of the recursion method
return 1;
else
return n * factorial(n - 1); //returns n * call of the method itself with until n == 1
}
public static void main(String[] args){ //main method to call the factorial method
Scanner input = new Scanner(System.in);
System.out.print("Enter a number: "); //prompts the user to enter a number
int n = input.nextInt(); //n variable represents user input
System.out.println("Factorial of " + num + " is: " + factorial(n)); //prints and call factorial(n) with n argument
}
Output:
run:
Enter a number: 4
Factorial of 4 is: 24
Example 2:
public static void myMethod(int counter){
if(counter == 0){
return;
}else{
System.out.println("Counter: " + counter);
myMethod(--counter);
return;
}
}
A call to myMethod(4) prints the following:
Output:
run:
Enter a number: 4
Counter: 4
Counter: 3
Counter: 2
Counter: 1
The Fibonacci sequence is a classic example of recursion:
In this example, the first and second numbers in the second Fibonacci sequence are 1. Thereafter, each number is the sum of its two immediate predecessors... see the output after the code or interpret the fibonacci(n) method in Example 3 as follows:
fibonacci(1) = 1 //returns 1 if n is == 1
fibonacci(2) = 1 //returns 1 if n is == 2
fibonacci(n) = fibonacci(n - 1) + fibonacci(n - 1) if n > 2
Example 3:
public static int fibonacci(int n){
if(n <= 2){ //condition used as the base case or stopping state of the recursion method
return 1; //returns 1 if n is less than or equal to 2
}else{
return fibonacci(n - 1) + fibonacci(n - 2);
}
}
public static void main(String[] args){
for(int i = 1; i <= 10; i++){
System.out.print(fibonacci(i) + " ");
}
}
Output:
1 1 2 3 5 8 13 21 34 55