Welcome back to the Digilent Blog! Today we’re going to go over recursion! Recursion is when a function calls itself directly, or through another function. Sometimes we can’t solve a problem using loops (iteration), so we have to use recursion. Recursion is slower than iteration, difficult to debug, and it uses up more of the stack. But recursion can also have simpler code, so in some cases, the benefits outweigh the problems.
There are two parts of a recursive function: the base case and the recursive call. The base case is when we reduce our function to the most basic case of our function, and then returns. The recursive call is when we call the recursive function again. This is confusing to read, so the best way to show it is with code. While we call the recursive statement, our function is pushing another call of itself with a reduced parameter input (otherwise the function will never end) onto the stack, and these calls are popped when we reach the base case and start to return.
Let’s check out the first function, the factorial. Factorial is simulating the “!” operator in mathematics. We have the parameter and return values be an integer, with parameter named as “n”. The first thing we see is the base case. If n <= 1 (n should never be 0 or less, but just in case, we have the “<” symbol) then we return 1.
Secondly, we have the recursive step, which is were we call factorial again in the return statement. Let’s use the example of “n” being 4, or recursive call will be return(4 * factorial(3)), with (n-1) being our reduction. Because the “n” being passed as the parameter is not our base case, we will do another recursive call, but this time it will be return(3 * factorial(2)).
Another good example case of recursion is the Fibonacci sequence. The Fibonacci sequence is the summation of the two previous entrees up to “n”. What’s new here is that we have two base cases that can happen, because our fibonacci uses the two previous numbers, meaning that it will have to call fibonacci twice for each recursive call. With each call of fibonacci puts two other calls of fibonacci onto the stack, so you can see how recursion can potentially cause stack problems!
All the recursive code
Here’s a small main function that lets users input a value. For this example, we’re limiting the user’s input values to be between 0 and 19. This is because for our factorial function, 20! and beyond is larger than the size of int (check out why here!).
