Compute factorial recursively

Summary

Write a recursive function to compute the factorial of a non-negative integer.

Problem statement

Given a non-negative integer n, return n! (n factorial) computed using recursion. Factorial of 0 is defined as 1. You should validate that n is an integer >= 0. For this exercise, assume inputs in tests are valid non-negative integers.

Task

Implement factorial(n) using recursion with proper base cases.

Examples

Input format

A single integer n supplied as an argument to factorial(n).

Output format

An integer representing n!.

Constraints

0 ≤ n ≤ 20 (results fit in Python int in tests). Use recursion; do not use math.factorial.

Samples