HintsToday

Recursion in python- recusrsive functions in detail

Recursion is a programming technique where a function calls itself directly or indirectly. Recursive functions are particularly useful for solving problems that can be broken down into smaller, simpler subproblems of the same type.

Key Concepts of Recursion

1. Base Case: The condition under which the recursion ends. Without a base case, a recursive function would call itself indefinitely, leading to a stack overflow.
2. Recursive Case: The part of the function where the function calls itself with a smaller or simpler argument.

Tips for Writing Recursive Functions

1. Identify the Base Case: Clearly define the simplest instance of the problem, which can be solved without further recursion.
2. Ensure Progress: Each recursive call should progress towards the base case, usually by simplifying the problem.
3. Test with Small Inputs: Start by testing the function with small input values to ensure the base and recursive cases are correctly defined.
4. Consider Iterative Solutions: Some problems are more efficiently solved with iteration rather than recursion, especially if they involve a large number of recursive calls, which can lead to stack overflow.

General Structure of a Recursive Function

def recursive_function(parameters):
    if base_case_condition:
        return base_case_value
    else:
        # Perform some operation
        return recursive_function(modified_parameters)

Examples of Recursive Functions

1. Factorial of a Number

The factorial of a non-negative integer nnn is the product of all positive integers less than or equal to nnn. It is denoted by n!n!n!.

n!=n×(n−1)!n! = n times (n-1)!n!=n×(n−1)!

Recursive Definition:

• Base case: 0!=10! = 10!=1
• Recursive case: n!=n×(n−1)!n! = n times (n-1)!n!=n×(n−1)!

Python Implementation:

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

# Testing the factorial function
print(factorial(5))  # Output: 120

2. Fibonacci Sequence

The Fibonacci sequence is a series of numbers where each number is the sum of the two preceding ones, usually starting with 0 and 1.

F(n)=F(n−1)+F(n−2)F(n) = F(n-1) + F(n-2)F(n)=F(n−1)+F(n−2)

Recursive Definition:

• Base case: F(0)=0F(0) = 0F(0)=0, F(1)=1F(1) = 1F(1)=1
• Recursive case: F(n)=F(n−1)+F(n−2)F(n) = F(n-1) + F(n-2)F(n)=F(n−1)+F(n−2)

Python Implementation:

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

# Testing the fibonacci function
print(fibonacci(7))  # Output: 13

3. Sum of a List

Calculate the sum of all elements in a list.

Recursive Definition:

• Base case: An empty list has a sum of 0.
• Recursive case: The sum of a list is the first element plus the sum of the rest of the list.

Python Implementation:

def sum_list(lst):
    if len(lst) == 0:
        return 0
    else:
        return lst[0] + sum_list(lst[1:])

# Testing the sum_list function
print(sum_list([1, 2, 3, 4]))  # Output: 10

4.for generating all permutations of a string

This function uses recursion to generate all permutations. The base case handles the simplest scenario where the string length is 1, returning the string itself in a list. For longer strings, it iterates through each character, removes it from the string, and recursively generates permutations of the remaining characters. These partial permutations are then combined with the removed character to form the full permutations.

Explanation:

• Base Case: When the length of the string is 1, return a list containing just that string.
• Recursive Case: For each character in the string, remove the character and recursively find permutations of the remaining substring. Prepend the removed character to each of these permutations and add them to the list of permutations.

Let’s break down the execution of the recursive permutations function step by step using the input "abc".

Step-by-Step Execution

1. Initial Call: permutations("abc")
   • The input string is "abc", which is longer than 1 character.
   • Initialize perms as an empty list: perms = [].
2. First Level of Recursion:
   • Loop over each character in "abc":
     • For i = 0 (character 'a'):
       • Remove 'a', remaining string: "bc".
       • Recursive call: permutations("bc").
3. Second Level of Recursion: permutations("bc")
   • The input string is "bc", which is longer than 1 character.
   • Initialize perms as an empty list: perms = [].
4. Second Level: Loop over "bc":
   • For i = 0 (character 'b'):
     • Remove 'b', remaining string: "c".
     • Recursive call: permutations("c").
5. Third Level of Recursion: permutations("c")
   • The input string is "c", which has only 1 character.
   • Base case: return ["c"].
6. Back to Second Level: Continue with "bc":
   • For i = 0 (character 'b'):
     • Combine 'b' with permutations of "c": 'b' + "c" = "bc".
     • Add to perms: perms = ["bc"].
   • For i = 1 (character 'c'):
     • Remove 'c', remaining string: "b".
     • Recursive call: permutations("b").
7. Third Level of Recursion: permutations("b")
   • The input string is "b", which has only 1 character.
   • Base case: return ["b"].
8. Back to Second Level: Continue with "bc":
   • For i = 1 (character 'c'):
     • Combine 'c' with permutations of "b": 'c' + "b" = "cb".
     • Add to perms: perms = ["bc", "cb"].
   • Return ["bc", "cb"] to the first level call.
9. Back to First Level: Continue with "abc":
   • For i = 0 (character 'a'):
     • Combine 'a' with permutations of "bc":
       • 'a' + "bc" = "abc".
       • 'a' + "cb" = "acb".
     • Add to perms: perms = ["abc", "acb"].
   • For i = 1 (character 'b'):
     • Remove 'b', remaining string: "ac".
     • Recursive call: permutations("ac").
10. Second Level of Recursion: permutations("ac")
    • The input string is "ac", which is longer than 1 character.
    • Initialize perms as an empty list: perms = [].
11. Second Level: Loop over "ac":
    • For i = 0 (character 'a'):
      • Remove 'a', remaining string: "c".
      • Recursive call: permutations("c").
12. Third Level of Recursion: permutations("c")
    • The input string is "c", which has only 1 character.
    • Base case: return ["c"].
13. Back to Second Level: Continue with "ac":
    • For i = 0 (character 'a'):
      • Combine 'a' with permutations of "c": 'a' + "c" = "ac".
      • Add to perms: perms = ["ac"].
    • For i = 1 (character 'c'):
      • Remove 'c', remaining string: "a".
      • Recursive call: permutations("a").
14. Third Level of Recursion: permutations("a")
    • The input string is "a", which has only 1 character.
    • Base case: return ["a"].
15. Back to Second Level: Continue with "ac":
    • For i = 1 (character 'c'):
      • Combine 'c' with permutations of "a": 'c' + "a" = "ca".
      • Add to perms: perms = ["ac", "ca"].
    • Return ["ac", "ca"] to the first level call.
16. Back to First Level: Continue with "abc":
    • For i = 1 (character 'b'):
      • Combine 'b' with permutations of "ac":
        • 'b' + "ac" = "bac".
        • 'b' + "ca" = "bca".
      • Add to perms: perms = ["abc", "acb", "bac", "bca"].
    • For i = 2 (character 'c'):
      • Remove 'c', remaining string: "ab".
      • Recursive call: permutations("ab").
17. Second Level of Recursion: permutations("ab")
    • The input string is "ab", which is longer than 1 character.
    • Initialize perms as an empty list: perms = [].
18. Second Level: Loop over "ab":
    • For i = 0 (character 'a'):
      • Remove 'a', remaining string: "b".
      • Recursive call: permutations("b").
19. Third Level of Recursion: permutations("b")
    • The input string is "b", which has only 1 character.
    • Base case: return ["b"].
20. Back to Second Level: Continue with "ab":
    • For i = 0 (character 'a'):
      • Combine 'a' with permutations of "b": 'a' + "b" = "ab".
      • Add to perms: perms = ["ab"].
    • For i = 1 (character 'b'):
      • Remove 'b', remaining string: "a".
      • Recursive call: permutations("a").
21. Third Level of Recursion: permutations("a")
    • The input string is "a", which has only 1 character.
    • Base case: return ["a"].
22. Back to Second Level: Continue with "ab":
    • For i = 1 (character 'b'):
      • Combine 'b' with permutations of "a": 'b' + "a" = "ba".
      • Add to perms: perms = ["ab", "ba"].
    • Return ["ab", "ba"] to the first level call.
23. Back to First Level: Continue with "abc":
    • For i = 2 (character 'c'):
      • Combine 'c' with permutations of "ab":
        • 'c' + "ab" = "cab".
        • 'c' + "ba" = "cba".
      • Add to perms: perms = ["abc", "acb", "bac", "bca", "cab", "cba"].
24. Final Result:
    • Return the final list of permutations: ["abc", "acb", "bac", "bca", "cab", "cba"].

Advanced Examples

1. Recursive Binary Search

Binary search is an efficient algorithm for finding an item from a sorted list of items.

Recursive Definition:

• Base case: If the list is empty, the item is not found.
• Recursive case: Compare the target with the middle element and recursively search in the appropriate half.

Python Implementation:

def binary_search(arr, target, low, high):
    if low > high:
        return -1  # Target is not found
    mid = (low + high) // 2
    if arr[mid] == target:
        return mid
    elif arr[mid] < target:
        return binary_search(arr, target, mid + 1, high)
    else:
        return binary_search(arr, target, low, mid - 1)

# Testing the binary_search function
arr = [1, 2, 3, 4, 5, 6, 7]
target = 5
print(binary_search(arr, target, 0, len(arr) - 1))  # Output: 4

2. Tower of Hanoi

The Tower of Hanoi is a classic problem where you have to move a set of disks from one rod to another, with the help of a third rod, following certain rules.

Recursive Definition:

• Base case: If there is only one disk, move it directly.
• Recursive case: Move n−1 n-1 n−1 disks to the auxiliary rod, move the nth disk to the target rod, then move the n−1 n-1 n−1 disks from the auxiliary rod to the target rod.

Python Implementation:

def tower_of_hanoi(n, source, target, auxiliary):
    if n == 1:
        print(f"Move disk 1 from {source} to {target}")
        return
    tower_of_hanoi(n - 1, source, auxiliary, target)
    print(f"Move disk {n} from {source} to {target}")
    tower_of_hanoi(n - 1, auxiliary, target, source)

# Testing the tower_of_hanoi function
tower_of_hanoi(3, 'A', 'C', 'B')
# Output:
# Move disk 1 from A to C
# Move disk 2 from A to B
# Move disk 1 from C to B
# Move disk 3 from A to C
# Move disk 1 from B to A
# Move disk 2 from B to C
# Move disk 1 from A to C

Recursive Function Design Principles

1. Define the Problem Clearly: Break down the problem into smaller subproblems that resemble the original problem.
2. Identify the Base Case(s): Ensure the recursion terminates by defining base case(s) that are simple and solvable without further recursion.
3. Simplify the Problem: Ensure each recursive call works on a simpler or smaller version of the problem, progressing towards the base case.
4. Avoid Redundant Calculations: Use techniques like memoization to store results of expensive recursive calls to avoid redundant calculations.
5. Test Thoroughly: Recursion can be tricky to debug. Test your recursive functions with a variety of inputs, including edge cases, to ensure correctness.

By mastering these principles and practicing with different problems, you’ll become proficient in writing and understanding recursive functions in Python.

Pages: 1 2 3 4 5