Python Program to Find Factorial of Number Using Recursion

Hi everyone! In this article, we’ll guide you through the Python program to find factorial of number using recursion. The [Problem Link] of which is attached here.

Examples

Example 1:

  Input: N = 5
  Output:  120
  Explanation: 5*4*3*2*1 = 120

Example 2:

  Input: N = 4
  Output:   24
  Explanation: 4*3*2*1 = 24

Your Task

You don’t need to read input or print anything. Your task is to complete the function factorial() which takes an integer “N” as input parameters and returns an integer, the factorial of “N”.

Expected Time Complexity: O(N)

Expected Space Complexity: O(1)

Constraints: 0 <= N <= 18

Solution of the Python Program to Find Factorial of Number Using Recursion

Problem Statement

Given: A non-negative integer “N”.

Task: Compute the factorial of the given number “N”. The factorial of a number “N” is the product of all positive integers less than or equal to “N”. It is denoted by “N!” and is defined as:

• 0! = 1
• 1! = 1
• For N > 1, N! = N × (N-1) × (N-2) × … × 1

Constraints: 0 <= N <= 20 (Assuming constraints based on typical factorial problems to prevent integer overflow in standard data types.)

Example 1:

  Input: N = 5
  Output: 120
  Explanation: 5! = 5 × 4 × 3 × 2 × 1 = 120

Example 2:

  Input: N = 0
  Output: 1
  Explanation: By definition, 0! = 1

Example 3:

  Input: N = 3
  Output: 6
  Explanation: 3! = 3 × 2 × 1 = 6

Also read about the Python Program to Print from 1 to N Without Loops.

Intuition and Approach

Objective: To calculate the factorial of a given non-negative integer “N” efficiently.

Understanding Factorial:

• Base Cases:
  • 0! = 1
  • 1! = 1
• Recursive Case: For N > 1, N! = N × (N-1)!

Approach Overview: The problem is a classic example of recursion, where the solution to a problem depends on solutions to smaller instances of the same problem.

Here’s how recursion applies to calculating factorial:

1. Recursive Function (func):
   • The function “func” is designed to compute the factorial of a given number “num”
   • It checks for the base cases (num == 0 or num == 1) and returns 1 directly
   • For other values, it calls itself with num – 1 and multiplies the result by “num”, effectively building up the factorial product.
2. Wrapper Function (factorial):
   • The factorial function serves as an interface to the recursive “func”
   • It takes the input number “N”, calls func(N), and returns the computed factorial

Why Recursion Works Here

• Simplicity: Recursion provides a straightforward way to express the factorial calculation, aligning closely with its mathematical definition.
• Breaking Down the Problem: By reducing the problem size (N to N-1), recursion handles each multiplication step systematically.
• Handling Base Cases: Recursion inherently manages the stopping condition through base cases, ensuring termination.

Code

class Solution:
    def func(self,num):
        if num==1 or num==0:
            return 1
        return num * self.func(num-1)
       
    def factorial(self, N):
        ans = self.func(N)
        return ans

The provided solution employs a recursive strategy to calculate the factorial of a given number. Here’s an integrated overview of how the code functions:

Recursive Function (func)

def func(self, num):
    if num == 1 or num == 0:
        return 1
        
    return num * self.func(num - 1)

1. Purpose: The “func” method is responsible for computing the factorial of the input number “num” recursively.
2. Mechanism:
   • Base Cases:
     • If “num” is 0 or 1, the function returns 1 immediately, as per the definition of factorial.
   • Recursive Case:
     • For num > 1, the function calls itself with num – 1 and multiplies the result by “num.” This builds the factorial product step by step.
3. Example Flow: For func(3):
   • func(3) calls func(2)
   • func(2) calls func(1)
   • func(1) returns 1
   • func(2) returns 2 * 1 = 2
   • func(3) returns 3 * 2 = 6

Explore about the Python Program to Print Divisors/Factors of an Integer.

Dry Run

To illustrate how the code operates, let’s walk through an example where N = 5.

Example:

• Input: N = 5
• Expected Output: 120 (since 5! = 5 × 4 × 3 × 2 × 1 = 120)

Edge Cases

Ensuring that the solution handles all possible edge cases is crucial for its robustness. Here are some noteworthy scenarios:

1. Zero (N = 0):
   • Input: N = 0
   • Expected Output: 1 (since 0! = 1)
   • Process:
     • factorial(0) calls func(0)
     • func(0) detects the base case and returns 1
   • Result: 1
   • Explanation: By definition, the factorial of zero is one
2. One (N = 1):
   • Input: N = 1
   • Expected Output: 1 (since 1! = 1)
   • Process:
     • factorial(1) calls func(1)
     • func(1) detects the base case and returns 1
   • Result: 1
   • Explanation: The factorial of one is also one
3. Single Digit Greater Than One (N = 2):
   • Input: N = 2
   • Expected Output: 2 (since 2! = 2)
   • Process:
     • factorial(2) calls func(2)
     • func(2) computes 2 * func(1) = 2 * 1 = 2
   • Result: 2
   • Explanation: Simple multiplication without carryover
4. Multiple Digits with Carryover (N = 5):
   • Input: N = 5
   • Expected Output: 120 (since 5! = 120)
   • Process:
     • factorial(5) calls func(5)
     • func(5) computes 5 * func(4) = 5 * 24 = 120
   • Result: 120
   • Explanation: Demonstrates handling of multiple recursive calls and multiplication
5. Large Number (N = 20):
   • Input: N = 20
   • Expected Output: 2432902008176640000 (since 20! = 2432902008176640000)
   • Process:
     • The recursive calls handle each decrement from 20 down to 1, multiplying sequentially
   • Result: 2432902008176640000
   • Explanation: Validates the function’s capability to handle larger inputs within the constraints
6. Negative Number (N = -1):
   • Input: N = -1
   • Expected Output:
     • Behavior: The current implementation does not handle negative numbers
     • Result: Potentially infinite recursion or incorrect results
   • Explanation: The function assumes “N” is a non-negative integer. Introducing negative numbers would lead to unintended behavior. To handle such cases, additional input validation should be incorporated.

You might also like to read about the Python Program to Check Armstrong Number.

Time and Space Complexity

Time Complexity: O(N)

• Explanation:
  • The “func” method makes a recursive call for each integer from “N” down to 0
  • Therefore, the number of recursive calls grows linearly with “N”
  • Each call performs a constant amount of work (a multiplication and a conditional check)
  • Overall: The time complexity scales linearly with the input size, O(N)

Space Complexity: O(N)

• Explanation:
  • Due to recursion, each function call adds a new frame to the call stack
  • For “N” recursive calls, the space used on the call stack grows linearly with “N”
  • Overall: The space complexity is linear, O(N), primarily due to the recursion depth

Note: While the time complexity is optimal for calculating factorials recursively, the space complexity can be a concern for very large values of “N” due to potential stack overflow. Iterative solutions can achieve O(1) space complexity but may sacrifice some of the elegance and simplicity of recursion.

For any changes to the document, kindly email at code@codeanddebug.in or contact us at +91-9712928220.