1. I can use recursion to solve problems faster!
Recursion is a process where a function calls itself. A function that does this is called a recursive function. If a function has a line of code that calls itself, then it’ll loop forever unless we have what is called a base condition. A Base Condition is the end of the line for recursive calling. Each recursive function needs a base condition that stops the function from calling itself and allows it to unravel.
You can think of recursion in programming just like you would think about it in mathematics. In math, a recursive function uses the previous number and some alterations to make the next number and so on.
Recursion can feel incredibly complex for us to wrap our heads around. At times, you’ll have very few lines of code in your program, but those same lines of code will solve very difficult problems and most of the execution will be behind the scenes.
Well… that made it sound like recursion should be avoided. It shouldn’t. You should use recursion because with it, we can uniquely solve problems with few lines of code that normally would be an absolute nightmare to hard code.
This example is not necessarily one where we would want to use recursion, but it allows an easy way to start thinking about recursion.
A recursive function needs two things. A call to itself, and a base condition. Each time the function is called, we need to adjust a value in order to get a different input. For instance, if we always send the function 1, then the same exact output would happen each time, but if we send it the value + 1, then we can expect different output while we work toward our base case. If we miss the base condition, then we will get a stackoverflow error. Essentially meaning that there will be nothing that stops our method from calling itself over and over again.
In this gist, you'll see a couple of interesting details. We generally always put an if statement that helps us control the flow of our recursion. What is really tricky about recursion is that each time the method calls itself, any code after that call is waiting to run until our recursion returns back from the base condition.
The n <= 1 condition would be our base condition because it stops the recursive call.
The else statement contains the recursive call
This example is getting closer to one where we would want to use recursion. We can calculate the fibonacci sequence using recursion by setting two base cases and uses two sets of recursion. If n == 0, we want to return 0. If n == 1, we want to return 1. This is because those are the first two numbers in the fibonacci sequence.
Then we have two sets of recursion. One for going back two numbers and another for going back one.
Now... we are cooking with fire. With recursion we can test if certain paths of a maze lead to an end and if they don't, backtrack to where we can tail off again!
Find the nth Factorial using recursion.
1. Write a program that allows the user to input an integer, and then uses recursion to find the factorial of that number!
2. This will be pretty similar to the way we found the fibonacci above, make sure you understand that one first! Ask me for help if you are struggling to start this one and I will help you brain storm ideas.
3. Think about what your base condition should be and then your recursive call.