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!