Identify a situation that requires the use of recursive thinking.
When should you use iteration, and when to use recursion?
There are (at least) these three factors to consider:
Iterative functions are typically faster than their recursive counterparts. So, if speed is an issue, you would normally use iteration.
If the stack limit is too constraining then you will prefer iteration over recursion.
Some procedures are very naturally programmed recursively, and all but unmanageable iteratively. Here, then, the choice is clear.
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.
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 making reference to further invocations, this saves the process from going on forever.
Example 1:
private static long factorial(int n){
int parameter
if (n == 1)
return 1;
else
return n * factorial(n - 1);
}
public static void main(String[] args){
Scanner input = new Scanner(System.in);
System.out.print("Enter a number: ");
int n = input.nextInt();
System.out.println("Factorial of " + num + " is: " + factorial(n));
}
Output
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:
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 output after the code or interpret the fibonacci(n) method in Example 3 as follows:
fibonacci(1) = 1
fibonacci(2) = 1
fibonacci(n) = fibonacci(n - 1) + fibonacci(n - 1) if n > 2
Example 3:
public static int fibonacci(int n){
if(n <= 2){
return 1;
}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
TAKE THE PRACTICE QUIZ HERE!