4 min read•Last Updated on June 18, 2024
Avanish Gupta
Avanish Gupta
Recursion We can use recursion in order to simplify repeated codes and loops.
Sometimes, you can break down a large problem or task by doing a subproblem repeatedly. This is called recursion. If this sounds like loops and iteration, it's because all recursive (the adjective form of recursion) methods can be written as a loop! We will learn how to use recursion effectively and see how this will simplify our code!
When writing recursion, notice how the code is much more simplified than if we were using loops. But, they will run slower, so we will sacrifice speed for conciseness in code. Recursive code has two main parts, the repeating/recursive part and the base case which makes sure we don't create an infinite loop in which our programs never stop.
Recursion is a way to simplify problems by having a subproblem that calls itself repeatedly. A recursive method has two parts: a base case and the recursive call. In the recursive call, the method basically calls itself, telling it to start over, either with the same parameters or different ones. After multiple calls, we approach the base case, where the recursion is stopped.
Here is its anatomy:
public static void recursiveMethod()
if (baseCaseCondition) { // base case
base case steps
} else {
do something
recursiveMethod(); // recursive call
}
}
The base case is the last recursive call. When the base case is reached, the recursion is stopped and a value is returned. The base case is the easiest part of the recursive call to write and should be written first to make sure that the program doesn't run forever.
The recursive calls are the different calls to the method. Each of the different recursive calls has different parameter values and leads up to the base case being reached. To write efficient recursion, recognize what the subtask is and what is different between each time the subtask is done. The subtask is the recursive call and what is different and stays the same are the parameters.
Whenever we have a recursive method, we have a call stack that keeps track of all the times that the recursive function is called, as well as their individual parameters. This is useful for when we have a function that has a recursive call in its return statement where the results of later recursive calls are used in past calls. Here is a picture demonstrating the call stack for recursion.
In this, x and e are the parameters of the recursive calls, and h is the result of the recursion that is passed back up. The recursive calls are made from top to bottom, while the recursive returns are passed from bottom to top. This is where tracing comes in handy, as shown in the picture above!
All recursion can be written as a loop, that is, all recursive code can be written iteratively. If we can just use iteration, why use recursion? The main answer? Simplicity. Recursive code is usually easier to read than iterative code. Is there a trade-off? Yes. This comes in the form of speed and memory. This is because the call stack takes up memory in your computer when running the program, and it takes time to pass up the recursive return values.
Here is an example of an iterative and recursive method to do multiplication using repeated addition:
Iterative Code:
public static int multiply(int a, int b) {
int sum = 0;
for (int i = 0; i < b; i++) {
sum += a;
}
return sum;
}
Recursive Code
public static int multiply(int a, int b) {
if (b == 0) {
return 0;
} else {
return multiply(a, b - 1) + a;
}
}
On the AP test FRQs, you can choose whether to write code iteratively or recursively, but you still have to know how recursion works for the AP exam!
We can write ArrayList traversal using recursion. As a reminder, here is the iterative code:
for (int i = 0; i < arrayList.size(); i++) {
System.out.println(arrayList);
}
Meanwhile, here is the recursive code:
public static void traverseArray(ArrayList<Integer> array, int startIndex) {
if (startIndex == array.size() - 1) { // base case
System.out.println(array.get(0));
} else { // recursive case
System.out.println(array.subList(startIndex, array.size()).get(0));
traverseArray(array, startIndex + 1)
}
}
//to use the above method
traverseArray(array, 0)
What This Method Is Doing
The recursion is actually getting the sublist of the big ArrayList with the first item in the sublist acting as the next item to be printed, and the last item in the sublist acts as the last item in the ArrayList. The base case is when there is only one item left in the sublist, at which point the last item is printed and the method stopped.
ArrayList is a dynamic data structure that allows you to store and manipulate collections of objects. Unlike arrays, ArrayLists can grow or shrink dynamically as needed.
Term 1 of 5
ArrayList is a dynamic data structure that allows you to store and manipulate collections of objects. Unlike arrays, ArrayLists can grow or shrink dynamically as needed.
Term 1 of 5
ArrayList is a dynamic data structure that allows you to store and manipulate collections of objects. Unlike arrays, ArrayLists can grow or shrink dynamically as needed.
Term 1 of 5
Recursion is a programming technique where a function calls itself to solve a problem by breaking it down into smaller, similar subproblems.
Base Case: The base case in recursion is the condition that stops the recursive calls and provides an answer or solution directly without further recursion.
Recursive Call: A recursive call refers to when a function invokes itself during its execution to solve a smaller version of the original problem.
Stack Overflow: A stack overflow occurs when there are too many recursive function calls, causing the program's call stack memory to be exhausted.
The call stack is a data structure that keeps track of function calls in a program. It stores information about the order and location of function calls, allowing the program to keep track of where to return after each function call is completed.
Recursion: A technique where a function calls itself directly or indirectly.
Stack Overflow: An error that occurs when there are too many nested function calls or recursive calls, causing the call stack to exceed its limit.
Function Call: The act of invoking or executing a specific function in a program.
Iterative code refers to programming constructs or algorithms that involve repetition using loops. It allows for executing a block of code multiple times until certain conditions are met.
Loop: A programming construct that repeats a block of code until certain conditions are met.
For Loop: A type of loop that iterates over an iterable object (such as lists) for a specified number of times.
While Loop: A type of loop that continues iterating as long as a given condition remains true.
ArrayList is a dynamic data structure that allows you to store and manipulate collections of objects. Unlike arrays, ArrayLists can grow or shrink dynamically as needed.
List Interface: A Java interface that defines common methods for working with lists.
add(): A method used to insert elements into an ArrayList.
remove(): A method used to delete elements from an ArrayList.
Traversal refers to the process of visiting and accessing each element in a data structure, such as an array or a tree, in a specific order.
Preorder traversal: A type of traversal where the root node is visited first, followed by its left subtree and then its right subtree.
Inorder traversal: A type of traversal where the left subtree is visited first, followed by the root node and then the right subtree.
Postorder traversal: A type of traversal where the left subtree is visited first, followed by the right subtree and then finally the root node.