Backtracking #
Recursion #
recursion is when a function calls itself, usually with a different input. This is known as a recursive function.
Time and Space Complexity #
Time: O(n)
In total, n calls are being made to the factorial function, where each function call is O(1), making the total time complexity O(n).
Space: O(n) While we aren’t using any data structures, recursion operates off of an implicit stack, known as the function call stack. That is how we are able to return from one function call to the previous one. Since there are n recursive calls, there will be n function calls placed on the stack, which results in O(n) space.