Lecture 55:- Nested Recursion

Nested recursion is a type of recursion in which a recursive function passes the result of a recursive call as a parameter to another recursive call. In other words, the function calls itself with the result of its own recursive call as an argument.

Here's an example of nested recursion in Python:

pythonCopy code

def nestedRecursion(n):    if n > 100:        return n - 10    else:        return nestedRecursion(nestedRecursion(n + 11)) # Call the nestedRecursion function result = nestedRecursion(95) print(result)  # Output: 91

In this example, the nestedRecursion function takes an integer n as input. If n is greater than 100, it subtracts 10 and returns the result. Otherwise, it calls itself twice with n + 11 as an argument.

The nested recursive calls create a recursive "tree" structure, where each level of recursion depends on the result of the previous level. The recursive calls continue until n becomes greater than 100, and then the intermediate results are unwound and propagated back up the recursion.

In the given example, when nestedRecursion(95) is called:

• The initial call passes 95 as the input.
• The first nested call is nestedRecursion(n + 11), which evaluates to nestedRecursion(106).
• The second nested call is nestedRecursion(nestedRecursion(n + 11)), which becomes nestedRecursion(nestedRecursion(106)).
• The innermost call nestedRecursion(106) evaluates to 96.
• The outer call nestedRecursion(nestedRecursion(106)) becomes nestedRecursion(96).
• Finally, the outermost call nestedRecursion(96) evaluates to 91, which is the final result.

Nested recursion can be a powerful technique for solving problems that require multiple levels of recursion and complex dependencies between recursive calls. However, it's important to ensure that proper termination conditions are in place to avoid infinite recursion.