Performance Comparison of Factorial Algorithms Implemented via Iteration and Recursion Over Both Numbers and BigInts

factorialComparison.ts

function factorialIterBigIntBackward(input: bigint): bigint {
    let computedFactorial = 1n;
    for (let i = input; i >= 1n; i--) {
        computedFactorial *= i;
    }
    return computedFactorial;
}

function factorialIterBigIntForward(input: bigint): bigint {
    let computedFactorial = 1n;
    for (let i = 1n; i <= input; i++) {
        computedFactorial *= i;
    }
    return computedFactorial;
}

function factorialRecBigIntBackward(input: bigint): bigint {
    function internalRecurse(current: bigint): bigint {
        if (current === input) {
            return current;
        } else {
            return current * internalRecurse(current + 1n);
        }
    }

    return internalRecurse(1n);
}

function factorialRecBigIntForward(input: bigint): bigint {
    if (input === 0n) {
        return 1n;
    } else {
        return input * factorialRecBigIntForward(input - 1n);
    }
}

function factorialTailRecBigInt(input: bigint, accumulatedResult: bigint = 1n): bigint {
    if (input === 0n) {
        return accumulatedResult;
    } else {
        return factorialTailRecBigInt(input - 1n, input * accumulatedResult);
    }
}

function factorialIterNumberBackward(input: number): number {
    let computedFactorial = 1;
    for (let i = input; i >= 1; i--) {
        computedFactorial *= i;
    }
    return computedFactorial;
}

function factorialIterNumberForward(input: number): number {
    let computedFactorial = 1;
    for (let i = 1; i <= input; i++) {
        computedFactorial *= i;
    }
    return computedFactorial;
}

function factorialRecNumberForward(input: number): number {
    if (input === 0) {
        return 1;
    } else {
        return input * factorialRecNumberForward(input - 1);
    }
}

function factorialRecNumberBackward(input: number): number {
    function internalRecurse(current: number): number {
        if (current === input) {
            return current;
        } else {
            return current * internalRecurse(current + 1);
        }
    }

    return internalRecurse(1);
}

function factorialTailRecNumber(input: number, accumulatedResult: number = 1): number {
    if (input === 0) {
        return accumulatedResult;
    } else {
        return factorialTailRecNumber(input - 1, input * accumulatedResult);
    }
}

function measurePerformanceOfFunction<T extends (...args: any) => any>({ functionToMeasure, paramsToCallWith, timesToMeasure }: { functionToMeasure: T, paramsToCallWith: Parameters<T>, timesToMeasure?: number }): number {
    timesToMeasure = timesToMeasure == null || timesToMeasure <= 0 ? 1 : timesToMeasure;

    let totalTime = 0;
    for (let i = 0; i < timesToMeasure; i++) {
        const start = performance.now();
        functionToMeasure.apply(null, paramsToCallWith);
        const end = performance.now();

        totalTime += end - start;
    }

    return totalTime / timesToMeasure;
}

const input = 5000;
const inputAsBigInt = BigInt(input);

const timesToMeasure = 50;

console.log(`Input: ${input}`)
console.log(`Measured: ${timesToMeasure} times`)

const start = performance.now()
console.table({
    'Iterative Backward': {
        'BigInt': `${measurePerformanceOfFunction({ functionToMeasure: factorialIterBigIntBackward, paramsToCallWith: [inputAsBigInt], timesToMeasure })}ms`,
        'Number': `${measurePerformanceOfFunction({ functionToMeasure: factorialIterNumberBackward, paramsToCallWith: [input], timesToMeasure })}ms`
    },
    'Iterative Forward': {
        'BigInt': `${measurePerformanceOfFunction({ functionToMeasure: factorialIterBigIntForward, paramsToCallWith: [inputAsBigInt], timesToMeasure })}ms`,
        'Number': `${measurePerformanceOfFunction({ functionToMeasure: factorialIterNumberForward, paramsToCallWith: [input], timesToMeasure })}ms`
    },
    'Recursive Backward': {
        'BigInt': `${measurePerformanceOfFunction({ functionToMeasure: factorialRecBigIntBackward, paramsToCallWith: [inputAsBigInt], timesToMeasure })}ms`,
        'Number': `${measurePerformanceOfFunction({ functionToMeasure: factorialRecNumberBackward, paramsToCallWith: [input], timesToMeasure })}ms`
    },
    'Recursive Forward': {
        'BigInt': `${measurePerformanceOfFunction({ functionToMeasure: factorialRecBigIntForward, paramsToCallWith: [inputAsBigInt], timesToMeasure })}ms`,
        'Number': `${measurePerformanceOfFunction({ functionToMeasure: factorialRecNumberForward, paramsToCallWith: [input], timesToMeasure })}ms`
    },
    'Tail Recursive': {
        'BigInt': `${measurePerformanceOfFunction({ functionToMeasure: factorialTailRecBigInt, paramsToCallWith: [inputAsBigInt], timesToMeasure })}ms`,
        'Number': `${measurePerformanceOfFunction({ functionToMeasure: factorialTailRecNumber, paramsToCallWith: [input], timesToMeasure })}ms`
    }
});
const end = performance.now();
console.log(`Runtime: ${end - start}ms`)

My expectation is that between an iterative and a recursive approach, the iterative approach should run faster than the recursive approach. The only thing I would expect to possibly change that would be if the two approaches were run in a language supporting tail call optimization.

The iterative approach is consistently faster than the recursive approach when run over the Number type. This matches my expectation.

The iterative approach is consistently slower than the recursive approach when run over the BigInt type. This does not match my expectation.

Interestingly enough, the above results were obtained while in Firefox. In Chrome, the iterative approach seems to always win as I was originally expecting.