Recursion

When writing programs we usually call different functions to perform a very specific task. We call sqrt to calculate the square root of a number, we call a function max or min to calculate the maximum or the minimum of numbers. Recursion is the process of calling the same function from itself. So, if we have implemented a function with a name f if somewhere in the body of f, we call the function f again (usually with different arguments), that would be a recursive call:

def f(n):                                   # Define a function named f
    print(f'f() called with argument {n}')  # Print on each call (for demonstration)
    if n <= 0:                              # Stop if n is negative
        print('Let\'s stop here...')
    else:                                   # Otherwise call f with a smaller number
        f(n - 1)

f(10)

This is what the program would print

f() called with argument 10
f() called with argument 9
f() called with argument 8
f() called with argument 7
f() called with argument 6
f() called with argument 5
f() called with argument 4
f() called with argument 3
f() called with argument 2
f() called with argument 1
f() called with argument 0
Let's stop here...

This is a toy example demonstrating how a very basic recursive function could be implemented. In more real-world scenarios, we usually do some computations inside functions and return values after those computations instead of just printing messages.

In algorithmic problems, recursion can be very useful especially when dealing with graphs, advanced sorting algorithms, or backtracking which we’ll cover later in the course. Recursive problems are very common, and sometimes it’s much easier to implement a recursive solution than an iterative one using loops.

Video preview — A video by Reducible - 5 Simple Steps for Solving Any Recursive Problem

The process of solving a large problem by recursively dividing it into smaller problems until reaching the smallest/easiest possible one can be best understood with the concept called “recursive leap of faith”.

Recursive Leap of Faith

When implementing a recursive solution to a problem, one usually creates a function that works by calling itself at some point. The part of calling itself is usually referred to as the recursive call.

The great part about recursive solutions is that one can assume that the function works correctly when called with some simple arguments, and then implement the correct behavior for the harder ones. Similar to calling other functions like sqrt, max, abs, etc., you can assume that the function works for some smaller/simpler arguments and call those to build the current result on top of those.

💡

The only requirement is to make sure the function will arrive at the base case (the simplest case). Otherwise, we would have an infinitely running recursive function and might get a StackOverflow!

As a demonstration of how one might have a computation inside a recursive function, we can try to calculate the sum of all the numbers from 0, 1, 2, …, n given a number n.

Let’s implement the sum function step-by-step. The first step is to make sure the function works properly for the simplest case (properly count the sum for n being 0 or 1):

def sum(n):
    print(f'sum({n})', end=' -> ')
    if n == 0:         # In case n is 0 => the sum is 0
        return 0       # Stop the function execution here
    if n == 1:         # In case n is 1 => the sum is 1
        return 1       # Stop the function execution here

print(sum(1))          # sum(1) -> 1
print(sum(0))          # sum(0) -> 0
print(sum(2))          # sum(2) -> None (as we haven't implemented this part)

Having this part of the function, we can already use the fact that sum(0) will always correctly return 0, while sum(1) will always return 1. The function will work correctly even if we call the sum function with arguments 0 or 1 from the sum function itself.

So, we can go one step further and implement the sum function for n = 2 and n = 3 by having the results for sum(1) and sum(0):

def sum(n):
    print(f'sum({n})', end=' -> ')
    if n == 0:
        return 0
    if n == 1:
        return 1
    if n == 2:             # If n is 2, we can add 2 to the result of sum(1) implemented above
        return n + sum(1)  # or `n + sum(n - 1)`
    if n == 3:             # If n is 3, we can add 3 to the result of sum(2) implemented above
        return n + sum(2)  # or `n + sum(n - 1)`

print(sum(1))          # sum(1) -> 1
print(sum(0))          # sum(0) -> 0
print(sum(2))          # sum(2) -> sum(1) -> 3
print(sum(3))          # sum(3) -> sum(2) -> sum(1) -> 6
print(sum(4))          # sum(4) -> None (as we haven't implemented this part)

This way, it’s obvious that the sum function works properly for small cases like n being equal to 0, 1, 2, or 3.

Having this, we can implement the function for other values of n larger than 3. The only requirement is to arrive at those smaller values of n (0, 1, 2, or 3) when calling the function sum from itself. So, for larger values of n, like 4, 5, or 6, etc. we can implement the sum function by using the fact that to calculate the sum(4), we can add 4 to the result of sum(3), while calculating the sum(5) can be done by adding 5 to the result of sum(4):

def sum(n):
    print(f'sum({n})', end=' -> ')
    if n == 0:
        return 0
    if n == 1:
        return 1
    if n == 2:
        return n + sum(1)
    if n == 3:
        return n + sum(2)
    # For all other cases (4, 5, 6, ...)
    return n + sum(n - 1)  

print(sum(2))          # sum(2) -> sum(1) -> 3
print(sum(3))          # sum(3) -> sum(2) -> sum(1) -> 6
print(sum(4))          # sum(4) -> sum(3) -> sum(2) -> sum(1) -> 10
# ...

The key parts of a recursive function are:

Base case: A condition that stops the recursion. Without this, the function would call itself indefinitely, causing an infinite loop. Here, it's n == 0 and n == 1.

Recursive step: Where the function calls itself, usually with a different argument. Here, it's sum(n - 1).

As the calls for n == 1, n == 2, and n == 3 are exactly the same as for n == 4, n == 5, etc., we can even simplify the sum function by having only 1 base case (for n == 0):

def sum(n):
    print(f'sum({n})', end=' -> ')
    if n == 0:
        return 0
    return n + sum(n - 1)  

print(sum(2))          # sum(2) -> sum(1) -> sum(0) -> 3
print(sum(3))          # sum(3) -> sum(2) -> sum(1) -> sum(0) -> 6
print(sum(4))          # sum(4) -> sum(3) -> sum(2) -> sum(1) -> sum(0) -> 10
# ...

This way, having the recursive leap of faith, we assume/know that the function works properly for smaller/simpler cases, and construct the rest of the function based on those simpler cases. That helps in understanding how recursive functions work and how they can be implemented.

💡

Calling the function recursively is like calling a completely different function that you know for sure will work with the passed arguments.

Challenge

Implement a recursive function that would calculate n! modulo .

Input

The input contains a single integer n (1 ≤ n ≤ 1000).

Output

The program should print the result of n! modulo .

Examples

Input	Output
5	120
10	3628800

Recursive Leap of Faith

Challenge

Input

Output

Examples

Constraints

To check your solution you need to sign in

Sign in to continue