Recursion in Python programming language

Recursion is a powerful tool in programming that allows us to solve complex problems by breaking them down into smaller, more manageable sub-problems. In this tutorial, we will explore the concept of recursion, how it works, and why it is an important concept in programming. We will learn how to write recursive functions in Python and how to use them to solve various problems. This tutorial is intended for beginner to intermediate Python programmers who want to expand their knowledge and understanding of this important concept in programming. So let's get started and dive into the world of recursion!

What is Recursion :

• Recursion is a programming technique where a function calls itself to solve a problem.
• Recursion is a technique for solving problems that can be broken down into smaller, simpler sub-problems. 
• A complex problem is broken into smaller, simpler instances until a base case is reached.
• Base Case :
  • The base case is the condition that stops the recursion and provides the result.
  • It is crucial to prevent infinite recursion and ensure the termination of the recursive function.

Recursive Function Structure :

• A recursive function consists of four main components :
  • Base Case : Check if the base case is met and return the result.
  • Recursive Call : If the base case is not met, make a recursive call to the function with a modified input.
  • Combining the Results : Combine the result from the recursive call with the current step of the function.
  • Return the Final Result : Return the final result obtained from the recursive calls.

Recursion Examples : 

• There are two classic examples in programming world to explain recursion.
• Here we'll show how these examples are implemented in Python.
• These examples are :
  • Factorial Calculation
  • Fibonacci Sequence

Factorial Calculation through recursion : 

• The factorial calculation is a classic example of a recursive function.
• It calculates the factorial of a non-negative integer n.
• The factorial of a number is the product of all the positive integers less than or equal to the number.
•  E.g. The factorial of 5 would be  5 * 4 * 3 * 2 * 1 =  120 .
• In this case the function would call itself with the number one less than the number it was originally called with. 
  • i.e the function was originally called with number 5
  • Then it calls itself with number one less than 5 i.e. 4
  • Then it calls itself with number 3, and so on.
• The base case is when n is 0, and the factorial is 1.
• The recursive call multiplies n by the factorial of n-1.
• Code Sample :

def factorial(n):
    if n == 0:
        print("Value of n = ", n)
        return 1
    else:
        print("Value of n = ", n)
        return n * factorial(n - 1)


fact = factorial(5)
print()
print("Final factorial value :", fact)

# Output
# Value of n =  5
# Value of n =  4
# Value of n =  3
# Value of n =  2
# Value of n =  1
# Value of n =  0

# Final factorial value : 120

Fibonacci Sequence through recursion :

• The Fibonacci sequence is another common example of recursion.
• It calculates the nth Fibonacci number.
• Fibonacci sequence starts with 1,1 and then each number is the sum of previous two numbers.
• E.g. for n = 7 Fibonacci sequence is  1,1,2,3,5,8,13 
• In above example our final result will be 13.
• The base case is when n is 0 or 1.
• The recursive call adds the previous two Fibonacci numbers to calculate the current one.
• Code Sample :

def fibonacci(n):
    if n <= 1:
        return n
    else:
        return fibonacci(n - 1) + fibonacci(n - 2)

fibo = fibonacci(7)
print()
print("Final Fibonacci value :", fibo)

# Output
# Final Fibonacci value : 13

Pros and Cons of Recursion :

Pros: 

• Concise and elegant solution for certain problems.
• Reflects the problem's inherent recursive nature, making the code more intuitive.

Cons:

• Recursion can lead to high memory consumption due to multiple function calls.
• Performance issues may arise for large inputs.

Recursion vs. Iteration :

• Recursion and iteration are two different approaches to problem-solving.
• Recursion is suitable for problems with repetitive sub-tasks or where the problem can be naturally divided into smaller instances.
• Iteration is generally more efficient, consumes less memory, and is suitable for linear operations.

Handling Recursion Depth :

• Python has a default recursion limit, which is the maximum depth of recursion allowed.
• If needed, you can modify the recursion limit using the  sys.setrecursionlimit()  function.

Tail Recursion Optimization :

• Tail recursion optimization is a technique to optimize recursive functions.
• It involves transforming the recursive function into an iterative one to improve performance.
• Helper functions and accumulator variables are used to implement tail recursion.

Recursive Data Structures :

• Recursive data structures are structures that contain references to objects of the same type.
• Examples include linked lists, trees, and graphs.
• Recursion can be used to traverse and manipulate these structures effectively.

Recursive Backtracking :

• Recursive backtracking is an algorithmic technique used to solve problems through systematic exploration of all possible solutions.
• It involves making a series of choices and undoing them if they lead to a dead end.
• An example is the N-Queens problem, where the task is to place N queens