08 Recurrence Relations and Summations

Recurrence Relations and Summations

  • Course Info: COP 3502C - Computer Science I, Spring 2025 by Yancy Vance Paredes, PhD.

Program Scenario

  • Task: Write a program to:

    • Prompt user for a whole number num.

    • Countdown from num to 1, printing one number per line.

    • Print "Done!" after the countdown.

Sample Run

  • Input: Enter Number: 5

  • Output:

    • 5

    • 4

    • 3

    • 2

    • 1

    • Done!

Main Function Structure

  • Code Snippet:

    int main(void) {
    int num;
    printf("Enter Number: ");
    scanf("%d", &num);
    // TODO: call function for countdown
    return 0;
}

Countdown Functions

  • Countdown Version 4:

    void countdown_v4(int n) {
    if(n >= 1) {
        printf("%d\n", n);
        countdown_v4(n-1);
    } else {
        printf("Done!\n");
    }
}

  • Countdown Version 5:

    void countdown_v5(int n) {
    if(n < 1) {
        printf("Done!\n");
        return;
    }
    printf("%d\n", n);
    countdown_v5(n-1);
}

Discussion

  • Explored recursive solutions.

  • Key Question: What is the running time complexity?

Recurrence Relation

  • Definition: Used to model running time T(n) of recursive solutions.

  • Characteristics:

    • Defines a sequence based on previous terms.

    • Expresses a function in terms of smaller input values.

Solving Recurrence Relations

  • Method: Iterative substitution method to expand recurrence step-by-step and identify patterns.

Caution

  • Familiarize with summation notation and closed-form versions for summation series.

Summation Notation Examples

  • Constant Summation: 5 + 5 + ... + 5 (n times)

  • Arithmetic Series: 1 + 2 + 3 + ... + n

Research and Application

  • Explore methods to manipulate summations.

Example: Tower of Hanoi

  • Objective: Move N disks from one pole to another with restrictions.

  • Constraints: Larger disks cannot be on top of smaller disks.

Tower of Hanoi Recursion

  • Code structure for the recursive solution demonstrates moving disks between poles.

  • Defined recursive function for disk movement with a base case check.

Recurrence for Tower of Hanoi

  • T(n) = 2T(n-1) + 1

  • Base case: T(1) = 1

  • Recursive structure leads to a closed form solution for the running time.

Sum of Geometric Series

  • Discussion of evaluating series of the form 1 + 2 + 4 + ... up to 2^(n-1).

Recap on Summations

  • Basic Summations, Arithmetic Series, Geometric Series, and their formulations.

Challenge Question

  • Analyze the running time complexity of the Fibonacci sequence solved recursively.

Discussion Highlights

  • Formulate recurrences for non-standard operations (like multiplication) to address complexities in recursive solutions.

Final Thoughts

  • Understanding and manipulating summations and recurrences are crucial for analyzing algorithm performance.