A recursive solution to get the factorial of n looks like this:
def fact(n):
if n == 0:
return 1
else:
return n * fact(n-1)
To understand what's going on here, let's break up the solution.
The if statement is what is called our base case. If n is 1, return 1 With out the base case, our program would loop infinitely.
The else statement makes a call to itself. It can be a bit confusing to think at first, but after a little practice, recursion starts to make sense.
Let's say that we want to find !3 (3*2*1). Let's call our factorial function with 3.
fact(3)
Since n is not 1, we will move on to our else statement. We are returning 3 * fact(2).
At this point, a new stack frame is created.
In this stack frame, we make yet another call to the factorial function and another stack frame is created.
We've reached our base case. fact(1) will return one. We can now retrace our steps to figure what those previous calls to the function evaluated to.
