Recursion

--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

number 1. So the operation will be seen like this.

var=5 * ( 4 * ( 3 * ( 2 * (1) ) ) )

That’s equal to 5*4*3*2*1. So the result is equal to 120.

Now you know how it works, your challenge now is to know how to use it.

Thanks for reading, any doubt in comments.

Special thanks to oadiazr from Taringa’s post.