--Originally published at Sierra's Blog
Recursion is what you have when you call a function inside a function, this can be done for different purpouses, the common example to explain recursions in python is a program that gives you the factorial of “n”:
def factorial(n):
if n == 1:
return 1
else:
return n * factorial(n-1)
x = factorial(5)
print (x)
the function gives you the factorial of number n, which in this case is 5. The function starts being factorial(5) but at the moment that it reads the underlined part the program it needs to start again to find what’s the answer of factorial(n-1) and it goes on and on till when n reaches number 1, then, after knowing what does every factorial(n-1) value is, it starts working backwards by multiplying the factorial * the current n number, here’s how python thinks:
Python: Ok, User’s asking me to save in the variable x whatever factorial(5) returns.
Python: I need to ejecute the function factorial(n). n isn’t equal to 1 so i’ll choose the else’s part.
Python: i’ll do this step by step
1.- n = 5… factorial(n) = n * factorial(n-1) = 5 * factorial(5-1) return 5 * factorial(4)
2.- n = 4… factorial(n) = n * factorial(n-1) = 4 * factorial(4-1) return 4 * factorial(3)
3.- n = 3… factorial(n) = n * factorial(n-1) = 3 * factorial(3-1) return 3 * factorial(2)
4.- n = 2… factorial(n) = n * factorial(n-1) = 2 * factorial(2-1) return 2 * factorial(1)
5.- n = 1… factorial(n), n == 1 then the if statement is true! i’ll return 1
Python: now I know what factorial(2) is: 2*1 = 2
Python: now i know what factorial(3) is: 3 * factorial(2) = 3 * 2 = 6
Python: now i know what factorial(4) is:
Continue reading "Recursions"