## Algorithm Name: Recursion
- #### Description:
- Should have the following properties to prevent an infinite loop:
- Base Case(s) - a terminating scenario that does not use recursion to produce and answer
- Set of rules, also known as recurrence relation, that reduces all other cases towards the base case
- #### Variations / Similar:
- #### Applicable Data Structures
- #### Key Parameters
- #### Diagram:
- #### General Use:
## Key Considerations
- #### Properties:
- Memoization - store intermediate results in the cache so that we can reuse them later without recalculation
- #### Implementation Details:
- Time Complexity:
- If it is just n number of calls, then it is equal to n * O(s) , where s is the complexity of the recursive function
- An execution tree can be used to denote the execution flow of a recursive function, where each node in the tree represents an invocation of the recursive function.
- This would form an n-ary tree where n is the number of times recursion appears in a recurrence relation.
- Determine the number of nodes in your n-ary tree to determine the complexity
- Take into account memoization that reduces number of nodes
- Space Complexity:
- Recursion Related Space
- A [[Stack]] is created to keep track of the recursive function calls; the stack tracks:
- Returning address of the function calls
- Parameters that are passed to the function call
- The local variables within the function call
- Exception: Tail Recursion
- Recursion where the recursive call is the final instruction in the recursion function. And there should be only one recursive call in the function
- #### General Tips
- #### Special Properties
## Specific Use Cases
- TBD