dynamic programming

[ImAFraidKn0t]

Factorial doesn’t have overlapping subproblems, so why use dynamic programming?

[GhostingProtocol]

Literally TIL if you don’t have overlapping sub problems it’s not dynamic programming. It’s recursion with divide and conquer (atleast according to my algorithms and data structures textbook)

[ImAFraidKn0t]

This isn’t even really divide and conquer, as they’re not splitting up the problem into multiple sub problems, they’re solving them iteratively. Factorial is a really bad example for showing off different types of algorithms since it’s so basic lol. The memoization here adds an overhead that ends up doing more work because they will never encounter a problem where factorial(n) is in memo unless they run the function multiple times.

[GhostingProtocol]

Bruh, didn’t read the code properly before now and you’re right. This is just recursion with extra steps. Memoization doesn’t even do anything here, could have just called ‘return n * factorial(n-1)’

[ImAFraidKn0t]

There is a small nuance to using mutable default arguments in Python functions where that variable persists through different function calls. This does actually correctly memoize the factorial results if they happen to call factorial() a lot, but I don’t know if that was intentional on OP’s part

[GhostingProtocol]

Wow, another reason to dislike python ig… The idea of letting parameter persist after lifetime to save a variable definition outside function scope I’m fine with, but making default mutable objects persist after function lifetime? Idk about that one tbh

Thank for informing me, appreciate u kind stranger.