What is Recursion? Explain with example.

• Recursion: Recursion is a technique used in programming where a function calls itself directly or indirectly. This allows the function to solve a problem by breaking it down into smaller instances of the same problem and recursively solving them. Recursion is a powerful tool that can be used to solve a wide variety of problems, including tree traversals, searching algorithms, and sorting algorithms.

• Example of Recursion: The classic example of recursion is the factorial calculation. The factorial of a non-negative integer n, denoted as n!, is the product of all positive integers from 1 to n. The factorial of 0 is defined to be 1. Here is a recursive definition of factorial:

factorial(n) = n * factorial(n-1), for n > 0
factorial(0) = 1

• Recursive Function: To implement this recursive definition in a programming language, we can use the following function:

def factorial(n):
    if n == 0:
        return 1
    else:
        return n * factorial(n-1)

• Base Case: The function checks if n is equal to 0. If it is, then the function returns 1. This is the base case of the recursion, which is the point at which the recursion stops.

• Recursive Call: If n is not equal to 0, then the function recursively calls itself with the argument n-1 and multiplies the result by n. This process continues until n reaches the base case, at which point the recursion stops and the function starts unwinding.

• Unwinding the Recursion: The function unwinds the recursion by returning the result of each recursive call to the previous call. The final result is returned to the initial call, which is typically the main function of the program.

• Time Complexity: The time complexity of a recursive algorithm is typically exponential, as the function calls itself repeatedly for smaller and smaller values of the input parameter. In the case of factorial calculation, the time complexity is O(n), where n is the input integer. This is because the function calls itself n times, and each recursive call takes constant time.

• Applications of Recursion: Recursion is used in a wide variety of applications, including:

• Tree traversals (e.g., depth-first search and breadth-first search)

• Searching algorithms (e.g., binary search and merge sort)

• Sorting algorithms (e.g., merge sort and quicksort)

• Numerical methods (e.g., solving differential equations and finding roots of polynomials)

• Parsing and compiling programming languages

• Creating fractals and computer graphics