Factorial of N

Given a non-negative integer N, compute N! (N factorial) using a recursive function. By definition, 0! = 1, and for N > 0, N! = N x (N-1)!. Implement the computation recursively and print the resulting value.

Input: A single line containing one non-negative integer N. Output: A single line containing N! as an integer.

0 <= N <= 20

Using a data type large enough to hold 20! (which is much larger than a 32-bit integer can represent) is essential here - factorials grow extremely fast, a good early lesson in checking numeric range limits before trusting a recursive formula.

Compute N factorial (N!) by defining it in terms of a smaller version of itself. Brute force: Compute the factorial with a simple iterative loop, multiplying a running product by each integer from 1 to N - this is actually just as efficient as the recursive version, and this problem specifically asks for the recursive approach to build recursion skills. Optimised: Recognizing that factorial(N) is defined directly in terms of factorial(N-1) is the essence of recursive thinking - each recursive call handles one 'layer' of the problem, trusting that the smaller call already correctly solves its own smaller version, until the base case is reached.

1. The BASE CASE: factorial(0) = 1, by definition. 2. The RECURSIVE CASE: factorial(N) = N * factorial(N-1) for N > 0. 3. Each call waits for the smaller call to return, then multiplies by N before returning its own result.

Time: O(N) - one recursive call per integer from N down to 0. Space: O(N), for the recursion call stack (N nested calls, each waiting for the one below it to return).

N = 0 must output 1 (base case). N = 20 produces the largest value in range (2432902008176640000) and must not overflow - use a 64-bit integer type.

Be ready to explain the TWO essential parts of any recursive solution clearly: the BASE CASE (which stops the recursion) and the RECURSIVE CASE (which reduces the problem toward that base case) - this problem is the cleanest possible example of both.