# Recursion
## Definition:
- In computer science, recursion is a method of solving a computational problem where the solution depends on solutions to smaller instances of the same problem. [source](https://en.wikipedia.org/wiki/Recursion_(computer_science)#)
- Most of the modern programming languages allow recursion by allowing the function to call itself within its own code.

## Fundamentals:
- ### Base Case:
  - The recursive function must have a base condition to terminate itself or the function shall end up in an infinite loop.
  - For example
    ```python
    def factorial(number):
        return number * factorial (number - 1)
    ```
    - Here, there is no condition to end the recursive call. Hence, the function will run infinitely until the its terminated.
    
    - This could be extremely dangerous as a non-terminating recursive program can lead to system crash.

    - Hence, a base case plays an extremely important role for recursive algorithms.

  - An example of a recursive function with a base condition:
    ```python
        def factorial(number):
            if number in (0, 1):
                return 1
            else:
                return number * factorial(number - 1)
    ```
    - Here, the function will stop its recursive call when the base condition is reached, hence terminating itself.

- ### Time Complexity: 
  
  - Time complexity of recursive algorithms depends on the following factors:
    1.   Total number of recursive calls
         -  A recursive function of input N that is called N times will have a runtime of O(N). 
    2.   Time complexity of additional operations for each recursive call.

- ### Interaction with computer memory:
- 
  - When a function is called, its memory is allocated on a stack. Stacks in computing architectures are the regions of memory where data is added or removed in a [last-in-first-out (LIFO)](https://www.geeksforgeeks.org/lifo-last-in-first-out-approach-in-programming/) process. Each program has a reserved region of memory referred to as its stack. When a function executes, it adds its state data to the top of the stack. When the function exits, this data is removed from the stack. [Source.](https://www.educative.io/courses/recursion-for-coding-interviews-in-python/B8wMXy0nmvk)

[More about recursion and its applications](https://www.educative.io/courses/recursion-for-coding-interviews-in-python/B8wMXy0nmvk)