Scribd Logo
Upload

Welcome to Scribd!

  • 15 views

    Lec12 EEE13 2s1617

    Uploaded by

    Nikko Angelo Dela Rosa
    This document discusses recursion and recursive backtracking. It provides examples of recursion in calculating factorials and Fibonacci numbers. Recursive backtracking is used to solve problems that cannot be easily solved with loops. It involves determining a base case and extending solutions. The time and space complexity of recursive functions depends on the number of calls and depth of recursion. Examples are analyzed, showing how complexity is calculated for different recursive problems and backtracking techniques.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd

    Lec12 EEE13 2s1617

    Uploaded by

    Nikko Angelo Dela Rosa
    15 views24 pages
    This document discusses recursion and recursive backtracking. It provides examples of recursion in calculating factorials and Fibonacci numbers. Recursive backtracking is used to solve problems that cannot be easily solved with loops. It involves determining a base case and extending solutions. The time and space complexity of recursive functions depends on the number of calls and depth of recursion. Examples are analyzed, showing how complexity is calculated for different recursive problems and backtracking techniques.

    Original Title

    Lec12_EEE13_2s1617

    Copyright

    © © All Rights Reserved

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    This document discusses recursion and recursive backtracking. It provides examples of recursion in calculating factorials and Fibonacci numbers. Recursive backtracking is used to solve problems that cannot be easily solved with loops. It involves determining a base case and extending solutions. The time and space complexity of recursive functions depends on the number of calls and depth of recursion. Examples are analyzed, showing how complexity is calculated for different recursive problems and backtracking techniques.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    15 views24 pages

    Lec12 EEE13 2s1617

    Uploaded by

    Nikko Angelo Dela Rosa
    This document discusses recursion and recursive backtracking. It provides examples of recursion in calculating factorials and Fibonacci numbers. Recursive backtracking is used to solve problems that cannot be easily solved with loops. It involves determining a base case and extending solutions. The time and space complexity of recursive functions depends on the number of calls and depth of recursion. Examples are analyzed, showing how complexity is calculated for different recursive problems and backtracking techniques.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    of 24

    EEE 13 LECTURE 12

    RECURSION AND RECURSIVE


    BACKTRACKING
    MOTIVATION

    RECURSION
    MOTIVATION

    RECURSION
    MOTIVATION

    ANOTHER WONDERFUL EXAMPLE


    See etiquette.c
    RECURSION

    REQUIREMENTS
    1. Base Case

    2. Rules/Recursion Body
    RECURSION

    HOW DO WE UTILIZE RECURSION?


    See factorial.cpp
    RECURSION

    ANOTHER EXAMPLE
    See fibonacci.cpp
    RECURSIVE BACKTRACKING

    WHAT ELSE CAN WE DO?


    With recursion, we can perform a technique called
    "Recursive Backtracking" to solve problems that cannot be
    easily solved using loops.
    RECURSIVE BACKTRACKING

    EXAMPLE 1
    See backtracking1.cpp
    RECURSIVE BACKTRACKING

    RECURSION AND STACKS

    f(0)

    f(1)

    f(2)

    f(3)

    f(4)

    f(5)
    RECURSIVE BACKTRACKING

    THOUGHT PROCESS
    1. Think about what you want to generate

    2. Determine the trivial solution

    3. Extend the trivial solution to get the next most trivial


    solution

    4. Continue until you can generalize

    5. Formulate the relationships between the solutions


    RECURSIVE BACKTRACKING

    WHY IS IT CALLED "RECURSIVE BACKTRACKING"?


    See backtracking2.cpp
    RECURSIVE BACKTRACKING

    WHY CAN’T WE USE LOOPS HERE?


    You can, but it will result in 1 extra loop for each string in the
    vector

    Imagine:

    for()

    for()

    for()

    …

    

    What if you don’t know the number of strings in the vector?
    RECURSIVE BACKTRACKING

    WHAT’S THE BASE CASE?

    A B C

    D E

    F G H
    ALGORITHM ANALYSIS

    LET’S BACKTRACK TO THE WONDERFUL EXAMPLE


    ‣ Was there a base case in the first place?

    > Yes, if in soft mode.

    ‣ How long will it take to reach the base case?



    > Constant at 333

    ‣ Is that dependent on anything variable?



    > No

    ‣ What is its time complexity?



    > O(1)

    ‣ What is its space complexity?



    > O(1) because the recursion is independent of any variable
    ALGORITHM ANALYSIS

    LOOKING AT THE FACTORIAL EXAMPLE…


    ‣ What was the base case?

    > 1! or 0! = 1

    ‣ How long will it take to reach the base case?



    > Around N recursive calls

    > O(N) space complexity

    ‣ What is the complexity of the function?



    > O(1)

    ‣ How many times was the function called?



    > Around N times

    ‣ What is its time complexity?



    > O(N)
    ALGORITHM ANALYSIS

    LOOKING AT THE FIBONACCI EXAMPLE…


    ‣ What was the base case?

    > fib(0) = 0, or fib(1) = 1

    ‣ How long will it take to reach the base case?



    > Around N calls

    > O(N) space complexity

    ‣ How many times is the base case visited?



    N
    > Around 2 times

    ‣ What is the complexity of the function in general?



    > O(1)

    ‣ What is its time complexity?



    N
    > O(2 )
    ALGORITHM ANALYSIS

    IN GENERAL…
    ‣ How many times was the function called (# of Calls) *
    Complexity of the function (Function Complexity)

    ‣ Time Complexity: O(# of Calls * Function Complexity)

    ‣ Space Complexity: O(Depth of the Recursion * Space


    Complexity of the Function)
    ALGORITHM ANALYSIS

    COMPLEXITY OF BACKTRACKING PROBLEM 1


    ‣ # of Calls

    > O(N) calls

    ‣ Complexity of the Function



    > O(1) (If no tabs)

    > O(N) (If with tabs)

    ‣ Time Complexity

    > O(N) or O(N2)
    ALGORITHM ANALYSIS

    COMPLEXITY OF BACKTRACKING PROBLEM 1


    ‣ Depth of Recursion

    > O(N)

    ‣ Space complexity of the function



    > O(1) (Simple Variables only)

    ‣ Space complexity:

    > O(N)
    ALGORITHM ANALYSIS

    COMPLEXITY OF BACKTRACKING PROBLEM 2


    ‣ # of Calls

    > O(M * N)

    M is the max length of a string in the array

    N is the size of the array

    ‣ Complexity of the Function



    > O(N)

    N is the size of the array

    ‣ Time Complexity

    > O(MN2)
    ALGORITHM ANALYSIS

    COMPLEXITY OF BACKTRACKING PROBLEM 2


    ‣ Depth of Recursion

    > O(N)

    N is the size of the array

    ‣ Space complexity of the function



    > O(N)

    N is the size of the array, and also the maximum length
    of your string

    ‣ Space complexity:

    > O(N2)
    ALGORITHM ANALYSIS

    OPTIMIZING THE SPACE COMPLEXITY OF BACKTRACKING PROBLEM 2

    ‣ Depth of Recursion

    > O(N)

    N is the size of the array

    ‣ Space complexity of the function



    > Reduced to O(1) since you don’t store a string in the
    function

    ‣ Space complexity:

    > O(N)
    SEE YOU NEXT
    WEEK :D

    You might also like