Recursion

#The Big Takeaway of this Unit

** Recursion: We can use recursion in order to simplify repeated code and loops.**

#Exam Weighting

• 5-7.5% of the test
• Roughly 2 to 3 multiple-choice questions

#Enduring Understanding

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!

#Building Computational Thinking

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.

#Main Ideas for the Unit 💡

• Intro to Recursion
• How to Code Recursive Methods
• Recursive Algorithms

#10.1 Recursion

Recursion is a method of solving a problem where the solution depends on solutions to smaller instances of the same problem. It involves dividing the problem into smaller pieces, and calling the same function to solve each piece. The function calls itself with a smaller version of the original problem, and this process is repeated until the problem is small enough to be solved directly.

Each recursive method is comprised of a base case and a recursive call. A base case is a condition you want to check to terminate the method. It should be the last time the recursive method calls itself. A recursive call usually comes after the base case and is when a function calls itself with a modified version of the original problem. The base case and the recursive call work together to solve the problem. The recursive call breaks the problem down into smaller pieces, and the base case provides a way to solve the problem directly when it becomes small enough. The function keeps calling itself with smaller and smaller versions of the problem until it reaches the base case, at which point the recursion stops and the final result is returned. If the base case is not defined correctly, or if the function does not stop calling itself, it can lead to an infinite loop. 🔁

Here is an example of using recursion in Java to find the factorial of a number. The factorial of a number is the product of all the numbers from 1 to that number. So, the factorial of 5 (written as 5!) is 5 * 4 * 3 * 2 * 1, or 120. public int factorial(int n) {

if (n == 1) {

return 1;

} else {

return n * factorial(n-1);

}

}

This function takes an integer n as an argument and returns the factorial of n. The base case is when n is equal to 1, in which case the function returns 1. For all other values of n, the function returns n multiplied by the factorial of n-1. Notice how the function calls itself inside the else statement, but modifies the argument being passed into it. This mea...