Python recursion function - what is going on here?

The function takes a number and calculates the factorial result.

So, for the value of 5 the result is 5 * 4 * 3 * 2 which is 120.

It makes sense to make that function a recursive one, because the factorial of 5 is 5 times the factorial of 4, the factorial of 4 is 4 times the factorial of 3 and so on. In the case that the function gets called with n = 1, the factorial is simply returned as 1 and the recursion can stop.

Consider this to be the actual algorithm running here:

1. factorial of 5 = 5 * factorial of 4
2. factorial of 4 = 4 * factorial of 3
3. factorial of 3 = 3 * factorial of 2
4. factorial of 2 = 2 * factorial of 1
5. factorial of 1 = 1

A version that might help:

def recursive(n): if n == 1: return 1 print ('n : {}'.format(n)) res = recursive(n-1) print ('return value is: {} (n={} * recursive({})={})'.format(n*res, n, n-1, res)) return res * n x = recursive(5) print('***** End result is: {}'.format(x)) 

Changes:

• Do not do recursive call twice
• Added some more debug output in the prints

Output:

n : 5 n : 4 n : 3 n : 2 return value is: 2 (n=2 * recursive(1)=1) return value is: 6 (n=3 * recursive(2)=2) return value is: 24 (n=4 * recursive(3)=6) return value is: 120 (n=5 * recursive(4)=24) ***** End result is: 120 

This is a very simple case, however, complex recursive methods can confuse anyone. I have found that tabbing each call (and its print messages) helps me understand what is happening. To do this you just need to pass down the recursion level (l) in each call:

def recursive(n, l=0): # l is the recurcion level if n == 1: return 1 print ('{} n : {}'.format(l * " ", n)) res = recursive(n-1, l + 1) print ('{} return value is: {} (n={} * recursive({})={})'.format( l * " ", n * res, n, n-1, res) ) return res*n 

This now formats things a little bit:

 n : 5 n : 4 n : 3 n : 2 return value is: 2 (n=2 * recursive(1)=1) return value is: 6 (n=3 * recursive(2)=2) return value is: 24 (n=4 * recursive(3)=6) return value is: 120 (n=5 * recursive(4)=24) ***** End result is: 120 

Your code is not really well fitted for a recursive begginer, so I attached here another code that outputs the same values as yours, but its easier to understand.

def recur(n): if n == 1: return n else: return n*recur(n-1) num = int(input("Enter a number: ")) if num < 0: print("Sorry, factorial does not exist for negative numbers") elif num == 0: print("The factorial of 0 is 1") else: print("The factorial of",num,"is",recur(num)) 

The recur function takes as input a natural number n. Now if n = 1, that means 1! = 1, which should be the output, no big deal. But otherwise the function will return your number n*recur(n-1). Example :

----Take n = 4 n = 1 -> false Now return (4) *recur(3) (3) * recur(2) (2) * recur(1) Now n = 1 and returns (1) 

All the numbers in brackets, (), will be added to the overall product, so 4 * 3 * 2 * 1 = 24. It is called recursive not because it calls itself, but because it starts backwards :)) Hope I lightened you a little bit!!

Extra Tip :

if n == 1: return n 

Here you can replace return n with return 1, will have the same output!

Following is an example of a recursive function to find the factorial of an integer.

def calc_factorial(x): """This is a recursive function to find the factorial of an integer""" if x == 1: return 1 else: return (x * calc_factorial(x-1)) num = 4 print("The factorial of", num, "is", calc_factorial(num)) 

the above example, calc_factorial() is a recursive function as it calls itself.

When we call this function with a positive integer, it will recursively call itself by decreasing the number.

Each function calls multiples the number with the factorial of number 1 until the number is equal to one. This recursive call can be explained in the following steps.

calc_factorial(4) # 1st call with 4 4 * calc_factorial(3) # 2nd call with 3 4 * 3 * calc_factorial(2) # 3rd call with 2 4 * 3 * 2 * calc_factorial(1) # 4th call with 1 4 * 3 * 2 * 1 # return from 4th call as number=1 4 * 3 * 2 # return from 3rd call 4 * 6 # return from 2nd call 24 # return from 1st call 

Our recursion ends when the number reduces to 1. This is called the base condition.

Every recursive function must have a base condition that stops the recursion or else the function calls itself infinitely.

Another example

A recursive function generally has two components:

• The base case is a condition that determines when the recursive function should stop
• The call to itself Here is an example to demonstrate both components:

# Assume that remaining is a positive integer def hi_recursive(remaining): # The base case if remaining == 0: return print('hi') # Call to function, with a reduced remaining count hi_recursive(remaining - 1) 

The base case for us is if the remaining variable is equal to 0 i.e. how many remaining "hi" strings we must print. The function simply returns.

After the print statement, we call hi_recursive again but with a reduced remaining value. This is important! If we do not decrease the value of remaining the function will run indefinitely. Generally, when a recursive function calls itself the parameters are changed to be closer to the base case.

Let's visualize how it works when we call hi_recursive(3):

After the function prints 'hi', it calls itself with a lower value for remaining until it reaches 0. At zero, the function returns to where it was called in hi_recursive(1), which returns to where it was called in hi_recursive(2) and that ultimately returns to where it was called in hi_recursive(3).