factorial_memoization.cpp File Reference

Factorial calculation using recursion and memoization More...

#include <cassert>
#include <cstdint>
#include <vector>

Include dependency graph for factorial_memoization.cpp:

Go to the source code of this file.

Classes
class	MemorisedFactorial

Functions
void	test_MemorisedFactorial_in_order ()
void	test_MemorisedFactorial_no_order ()
int	main ()
	Main function to run tests.

Detailed Description

Factorial calculation using recursion and memoization

This program computes the factorial of a non-negative integer using recursion with memoization (top-down dynamic programming). It stores intermediate results to avoid redundant calculations for improved efficiency.

Memoization is a form of caching where the result to an expensive function call is stored and returned. Example: Input: n = 5 Output: 120

Explanation: 5! = 5 × 4 × 3 × 2 × 1 = 120

The program uses a recursive function which caches computed results in a memo array to avoid recalculating factorials for the same numbers.

Time Complexity: O(n) Space Complexity: O(n)

Definition in file factorial_memoization.cpp.

Function Documentation

main()

int main

(

void

)

Main function to run tests.

Returns

0 on program success

Definition at line 61 of file factorial_memoization.cpp.

           {
    test_MemorisedFactorial_in_order();
    test_MemorisedFactorial_no_order();
    return 0;
}

test_MemorisedFactorial_in_order()

void test_MemorisedFactorial_in_order

(

)

Definition at line 44 of file factorial_memoization.cpp.

                                        {
    auto factorial = MemorisedFactorial();
    assert(factorial(0) == 1);
    assert(factorial(1) == 1);
    assert(factorial(5) == 120);
    assert(factorial(10) == 3628800);
}

test_MemorisedFactorial_no_order()

void test_MemorisedFactorial_no_order

(

)

Definition at line 52 of file factorial_memoization.cpp.

                                        {
    auto factorial = MemorisedFactorial();
    assert(factorial(10) == 3628800);
}