--Originally published at Hector Martinez Alcantara
Let’s talk about recursion. Personally, recursion is the most dificult thing in programming, but I’ll try to explain it by the most common recursive function, the factorial.
Let’s see the example code:
def factorial(var):
if var>1:
var=var*factorial(var-1)
return var
else:
return 1
x=int(input("Type a number to calculate the factorial:\n"))
print("The factorial of "+str(x)+" is:")
print(factorial(x))
The result of this is:
Type a number to calculate the factorial:
5
The factorial of 5 is:
120
But why?
Let’s see step by step, what happens.
First of all, we call the function with one parameter.
factorial(5) #factorial of 5
The number 5 enters to the function then if the number is 1 it returns 1, and then, the interesting part, if there’s some number higher than 1 the next function will be realized
var=var* factorial(var-1)
What happen here? Let’s see step by step.
First the value is 5, it’s greater than 1, so the function will be
var= 5 * factorial(var-1)
Now we can see that the value of factorial var-1 will be the same function, so we can see that the value of var in the function will be 4 that part will be like this:
var= 5 * (4*factorial((var-1)-1)
As you can see the value of the function factorial is the same function nested in the other sentence, so I’m goin to show you how the function looks doing the same procedure.
var=5 * ( 4 * ( 3 * ( 2 * (factorial ((((var-1)-1)-1)-1) ) ) ) )
#Remember the var==5
#((((var-1)-1)-1)-1) is like ((((5-1)-1)-1)-1) == 1
So…
var=5 * ( 4 * ( 3 * ( 2 * (factorial(1) ) ) )
What happens with factorial of 1? Remember that we typed that if the variable of the function is 1 or less, then the function will return
Continue reading "Recursion" →