Write a recursive function fact(n) that returns the factorial of a number n.
Concepts
- Recursion: Repeatedly multiply
nwithfact(n - 1). - Base Case:
fact(1) = 1 - Recursive Case:
n * fact(n - 1)
Time & Space Complexity
- Time Complexity:
O(n) - Space Complexity:
O(n)(recursive stack)
Examples
Input: 5
Output: 120 (5 * 4 * 3 * 2 * 1)Approach
- If
n == 1, return 1 (base case). - Else, return
n * fact(n - 1).
function fact(n) {
if (n === 1) return 1;
return n * fact(n - 1);
}
console.log(fact(5)); // Output: 120
#include <stdio.h>
int fact(int n) {
if (n == 1) return 1;
return n * fact(n - 1);
}
int main() {
printf("%d\n", fact(5)); // Output: 120
return 0;
}
#include <iostream>
using namespace std;
int fact(int n) {
if (n == 1) return 1;
return n * fact(n - 1);
}
int main() {
cout << fact(5) << endl; // Output: 120
return 0;
}
public class Main {
public static int fact(int n) {
if (n == 1) return 1;
return n * fact(n - 1);
}
public static void main(String[] args) {
System.out.println(fact(5)); // Output: 120
}
}
def fact(n):
if n == 1:
return 1
return n * fact(n - 1)
print(fact(5)) # Output: 120
using System;
class Program {
static int Fact(int n) {
if (n == 1) return 1;
return n * Fact(n - 1);
}
static void Main() {
Console.WriteLine(Fact(5)); // Output: 120
}
}
