Understanding Recursion

1. Understanding Recursion

In this video, we will discover what recursion is. Let's start!

2. Definition

Recursion is the term used to refer to a function calling itself. In almost all the situations where we use loops, we can substitute the loops using recursion. Recursion can solve problems that seem very complex at first.

3. Example - factorial

Let's study the factorial calculation. The factorial of an integer number is written as shown. It is the product

4. Example - factorial

of itself and all the integers below it. For example, the factorial of five will be five, multiplied by four, multiplied by three, multiplied by two, and multiplied by one. We can implement the factorial of a number with the following code. We define the result variable and initialize it to one. While n is bigger than one, we multiply it with the result, and subtract one from n. We can execute this code as shown and get the result.

5. Example - factorial using recursion

Using recursion, the factorial calculation can be written as shown, that is, n multiplied by the factorial of n minus one. We can first think about writing this code to implement it, but this algorithm would be executed forever!

6. Example - identifying the base case

To avoid infinite recursion, the first thing we are going to do is identify the base case. In recursion, the base case is used to add a condition that ensures that our algorithm doesn't execute forever. In the factorial, the calculation finishes when the n is equal to one, so we will add this condition to our algorithm. In the base case, we don't have to make any recursive calls, so we will return one, as the factorial of one is one. If n has any other value, we will then make the recursive call. We can now execute this code.

7. How recursion works

When using recursion, the computer uses a stack to keep track of the functions. This stack is called the call stack. In the factorial example we saw,

8. How recursion works

the computer will start calling factorial(5), but before the function finishes, it calls factorial(4). The computer needs to know that factorial(5) didn't finish, so it pushes this information into the call stack. It happens

9. How recursion works

the same way with the rest

10. How recursion works

of the

11. How recursion works

calls.

12. How recursion works

factorial(1) finishes without making any recursive call and returns one. Now factorial(2) receives the result of factorial(1). The execution of factorial(2) continues. When factorial(2) finishes,

13. How recursion works

it returns two,

14. How recursion works

and its item is popped from the stack. It happens the same way

15. How recursion works

for the

16. How recursion works

rest of the

17. How recursion works

calls.

18. Dynamic programming

Let's briefly study dynamic programming, an optimization technique mainly applied to recursion. It can reduce the complexity of recursive algorithms. It can be used for any problem that can be divided into smaller subproblems that overlap. The solutions of the subproblems are saved, avoiding recalculating them if needed later. This can be done with the memoization technique. We will practice all these in the exercises.

19. Let's practice!

Great job! Let's do some exercises about recursion!

Create Your Free Account

By continuing, you accept our Terms of Use, our Privacy Policy and that your data is stored in the USA.