Despite returning a call to n * findFactorialRecursively(n - 1)
, the solution to the last exercise did not change the output:
Execution context: 4 Execution context: 3 Execution context: 2 Execution context: 1 0
Why is the returned value not equal to the product of n
in each execution context? The short answer: we didn’t define a base case. To understand the need for a base case, it’s worth discussing the call stack that Swift creates for:
return n * findFactorialRecursively(of: n - 1)
Swift would create a call stack with the following events:
findFactorialRecursively(of: 3)
=3 * findFactorialRecursively(of: 2)
findFactorialRecursively(of: 2)
=2 * findFactorialRecursively(of: 1)
findFactorialRecursively(of: 1)
=1 * findFactorialRecursively(of: 0)
The return value associated with each function call depends on the value returned by n - 1
. Do you remember what our function returns when n
is equal to 0
?
Because our current implementation returns 0
when n
is zero, each product in the above call-stack, starting with event 3
, will be multiplied by 0
. This leads to a 0
solution for each of the contexts above it.
We can fix this with a base case. When the base case is met (n == 0
), the factorial method should return a number other than zero.
Instructions
We mentioned previously that 0!
is equal to 1
, so our base case is 0!
. When this condition is met, the function should return 1
.
Remove return 0
from the end of the function.
Add an else
block that returns 1
when the n
is not greater than 0
.