This challenge asks you to calculate the factorial of a number using recursion.

Sample Input:

3 #factorial

Sample Output:

6 #3*2*1

Recursion is when a function calls itself one or more times in order to solve a problem.

Imagine a factorial problem: 5!
n! can be rewritten as n*(n-1)!

5! = 54!
4! = 43!
3! = 32!
2! = 21!
1! = 10!
At this point, when n = 1, it just becomes 1 and doesn’t call the function again. Otherwise you’d keep going like below:
0! = 0-1!
-1 = -1*-2!
…

So, as long as n > 1, we want to keep calling n*(n-1)! until n becomes 1.

def factorial(n):
    if n > 1:
        return n * factorial(n-1) #recursive case
    else:
        return 1 #base case

factorial(3)

Below is a walkthrough of the logic: The factorial function is first called with n = 3. 3 is greater than 1 so it returns 3 x factorial(2).
We now have: 3 x factorial(2)
When factorial(2) is called, n = 2 and 2 is greater than 1 so it returns 2 x factorial(1).
We now have: 3 x 2 x factorial(1)
When factorial(1) is called, n = 1 and 1 is not greater than 1, so 1 is returned.
We now have: 3 x 2 x 1 = 6.
In the function above, the function continues to call itself until it reaches the base case of 1, where recursion is no longer called.

Another problem that could use recursion is the Fibonacci sequence. In this sequence, any number from value 2 (index 3) on is equal to Fn = Fn-1 + Fn-2. E.g. 1 1 2 3 5 8… Below is a recursive function fib that finds the fibonacci number Fn given the index n.

def fib(n): 
    if n >= 3:
        return fib(n-2) + fib(n-1)  #recursive case
    else:
        return 1 #base case
fib(6) #should return value at index 6, which is 8.

Below is a walkthrough of the logic: The fibonacci function is first called with index n = 6. 6 is greater than or equal to 3 so it returns fib(4) + fib(5).
We now have: fib(4) + fib(5)
When fib(4) is called, n = 4 and 4 is greater than or equal to 3 so it returns fib(2) + fib(3). When fib(5) is called, n = 5 and 5 is greater than or equal to 3 so it returns fib(3) + fib(4).
We now have: fib(2) + fib(3) + fib(3) + fib(4)
When fib(2) is called, n = 2 and 2 is not greater than or equal to 3 so it returns 1. When fib(3) is called, n = 3 and 3 is greater than or equal to 3 so it returns fib(1) + fib(2). When fib(4) is called, n = 4 and 4 is greater than or equal to 3 so it returns fib(2) + fib(3)
We now have: 1 + fib(1) + fib(2) + fib(1) + fib(2) + fib(2) + fib(3)
In fib(1) and fib(2), n <= 3 so they return 1. fib(3) again returns fib(1) + fib(2).
We now have: 1 + 1 + 1 + 1 + 1 + 1 + fib(1) + fib(2)
Again, in fib(1) and fib(2), n <= 3 so they return 1.
We now have: 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 = 8

Sample Solution:

#!/bin/python3

import math
import os
import random
import re
import sys

# Complete the factorial function below.
def factorial(n):
    if n > 1:
        return n * factorial(n-1)
    else:
        return 1


if __name__ == '__main__':
    fptr = open(os.environ['OUTPUT_PATH'], 'w')

    n = int(input()) #assume n is between 2 and 12

    result = factorial(n)

    fptr.write(str(result) + '\n')

    fptr.close()