Recursion Flashcards

Recursion

Introduction to Recursion

• Recursion is a fundamental programming technique offering elegant solutions to certain problems.
• Key aspects include:
  • Thinking recursively.
  • Programming recursively.
  • Correct usage of recursion.
  • Illustrative examples.

Recursive Definitions

• Recursion: Solving a problem by reducing it to smaller instances of itself.
• Recursive Definition: Expressing a problem in terms of its smaller version(s).
• Base Case: Essential condition(s) that directly provide a solution without further recursion.

Infinite Recursion

• Base Case Requirement: All recursive definitions must include a non-recursive base case to ensure termination.
• Infinite Recursion: Absence of a base case leads to a non-terminating recursive path.
• Analogy: Similar to an infinite loop, but inherent in the definition itself.

Recursive Factorial

• Definition: For a positive integer N, N! is the product of all integers from 1 to N.
• Recursive Expression:
  • 1! = 1
  • N! = N * (N-1)!
• Base Case: The recursion eventually reaches the base case of 1!.

Recursive Definitions (continued)

• 0! = 1
• n! = n \times (n-1)! if n>0
• Example Calculation:
  • 3! = 3 \times 2!
  • 2! = 2 \times 1!
  • 1! = 1 \times 0!
  • 0! = 1
  • 1! = 1
  • 2! = 2 \times 1 = 2 \times 1 = 2
  • 3! = 3 \times 2! = 3 \times 2 = 6

Computing Factorial (Illustrative Animation)

• Base case: factorial(0) = 1
• Recursive case: factorial(n) = n * factorial(n-1)
• factorial(4) is computed through a series of recursive calls.

Step-by-Step Factorial Computation

• factorial(4) = 4 * factorial(3)
• factorial(4) = 4 * 3 * factorial(2)
• factorial(4) = 4 * 3 * (2 * factorial(1))
• factorial(4) = 4 * 3 * (2 * (1 * factorial(0)))
• factorial(4) = 4 * 3 * (2 * (1 * 1))
• factorial(4) = 4 * 3 * (2 * 1)
• factorial(4) = 4 * 3 * 2
• factorial(4) = 4 * 6
• factorial(4) = 24

Recursive Factorial Method in Java

public static int fact(int num) {
    if (num == 0)
        return 1;
    else
        return num * fact(num - 1);
}

Quick Check: Recursive Definition of 5 * n

• Base case: 5 * 1 = 5
• Recursive case: 5 * n = 5 + (5 * (n-1))

Recursive Programming

• Recursive Method: A method that calls itself.
• Structure: Must handle both the base case and the recursive case.
• Execution Environment: Each call creates a new environment with new parameters and local variables.
• Control Flow: Upon completion, control returns to the calling method (which may be an earlier invocation of itself).

Recursive Definitions (continued)

• Recursive Algorithm: Solves a problem by reducing it to smaller instances.
• Base Case: Essential to stop the recursion, providing a direct solution.
• Recursive Method: Implements the recursive algorithm by calling itself.
• General Solution: Breaks down the problem into smaller versions.
• General Case: Calls a smaller version of itself and must eventually lead to the base case.

Designing Recursive Methods

1. Understand problem requirements.
2. Determine limiting conditions.
3. Identify base cases.

Sum of 1 to N

• Problem: Compute the sum of all numbers between 1 and a positive integer N.

Recursive Implementation for Summation

public int sum(int num) {
    int result;
    if (num == 1)
        result = 1;
    else
        result = num + sum(num-1);
    return result;
}

Recursive Programming Considerations

• Efficiency: While recursion can solve problems, it's not always the best approach.
• Understandability: Iterative solutions are often easier to understand for simple problems like summation.
• Elegance: Recursion can provide cleaner solutions for some problems.
• Decision: Carefully evaluate whether recursion is the correct technique for a given problem.

Indirect Recursion

• Direct Recursion: A method calls itself directly.
• Indirect Recursion: A method calls another method, which eventually calls the original method again (e.g., m1 calls m2, which calls m3, which calls m1).
• Complexity: Requires the same care as direct recursion but can be more difficult to trace and debug.

Largest Value in Array (Recursive Approach)

• Base Case: If the list size is 1, the largest element is the only element.
• Recursive Step: To find the largest element in list[a]…list[b]:
  • Find the largest element in list[a + 1]…list[b] and call it max.
  • Compare list[a] and max.
    • If list[a] >= max, the largest element is list[a].
    • Otherwise, the largest element is max.

public static int largest(int[] list, int lowerIndex, int upperIndex) {
    int max;
    if (lowerIndex == upperIndex)
        return list[lowerIndex];
    else {
        max = largest(list, lowerIndex + 1, upperIndex);
        if (list[lowerIndex] >= max)
            return list[lowerIndex];
        else
            return max;
    }
}

Execution of Largest

• Example: largest(list, 0, 3) with list = {5, 10, 12, 8}

Recursive Fibonacci

• Definition: rFibNum(a, b, n)
  • a if n = 1
  • b if n = 2
  • rFibNum(a, b, n-1) + rFibNum(a, b, n-2) if n>2.

public static int rFibNum(int a, int b, int n) {
    if (n == 1)
        return a;
    else if (n == 2)
        return b;
    else
        return rFibNum(a, b, n -1) +
               rFibNum(a, b, n - 2);
}

Fibonacci Numbers

• Fibonacci Series: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89,…
• Indices: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11
• Recursive Definition:
  • fib(0) = 0
  • fib(1) = 1
  • fib(index) = fib(index -1) + fib(index -2) for index >= 2
• Example: fib(3) = fib(2) + fib(1) = (fib(1) + fib(0)) + fib(1) = (1 + 0) + fib(1) = 1 + fib(1) = 1 + 1 = 2

Fibonacci Numbers (cont.)

• Illustrates the call order and return values for fib(4), showcasing multiple calls to fib(1) and fib(0).

Recursive Palindrome in Java

public class RecursivePalindrome {
    public static boolean isPalindrome(String s) {
        return isPalindrome(s, 0, s.length() - 1);
    }

    private static boolean isPalindrome(String s, int low, int high) {
        if (high <= low) // Base case
            return true;
        else if (s.charAt(low) != s.charAt(high)) // Base case
            return false;
        else
            return isPalindrome(s, low + 1, high - 1);
    }

    public static void main(String[] args) {
        System.out.println("Is moon a palindrome? " + isPalindrome("moon"));
        System.out.println("Is noon a palindrome? " + isPalindrome("noon"));
        System.out.println("Is a a palindrome? " + isPalindrome("a"));
        System.out.println("Is aba a palindrome? " + isPalindrome("aba"));
        System.out.println("Is ab a palindrome? " + isPalindrome("ab"));
    }
}

Characteristics of Recursion

• Base Cases: One or more base cases are used to stop recursion.
• Reduction: Every recursive call reduces the original problem, bringing it closer to a base case.
• Subproblems: Recursion solves a problem by breaking it into subproblems.
• Resemblance: If a subproblem resembles the original problem, the same approach can be applied recursively.
• Smaller Size: Subproblems are almost the same as the original problem but with a smaller size.