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
Most of the modern programming languages allow recursion by allowing the function to call itself within its own code.

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
```
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:
```
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:
- Total number of recursive calls
- Time complexity of additional operations for each recursive call.