Scribd Logo
Upload

Welcome to Scribd!

  • 40 views

    COMP 352 Data Structures and Algorithms: Recursion

    Uploaded by

    aikfirki
    Comp 352 Concordia Winter 2018 class notes

    Copyright:

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

    COMP 352 Data Structures and Algorithms: Recursion

    Uploaded by

    aikfirki
    40 views40 pages
    Comp 352 Concordia Winter 2018 class notes

    Original Title

    Recursion

    Copyright

    © © All Rights Reserved

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    Comp 352 Concordia Winter 2018 class notes

    Copyright:

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

    COMP 352 Data Structures and Algorithms: Recursion

    Uploaded by

    aikfirki
    Comp 352 Concordia Winter 2018 class notes

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    You are on page 1of 40

    COMP 352

    Data Structures and


    Algorithms

    RECURSION
    Chapter 5

    1
    Towers of Hanoi puzzle. Boggle

    Boggle Game

    Flow Free online

    The 8 puzzle 2
    Recursion in action
     Quick Sort
     Merge Sort
     All N-Log Sort
     Tree traversals
     XML Parsers
     HTML Parsers
     Backtracking Algorithm
     Binary Space Partitioning (BSP) Trees used for collision detection in
    game development.
     Recursive-descent language parsers
     Simulating state machines
     Lists (Linked Lists)
     Graphs
     Inductive reasoning used in AI
     Fractals ………

    3
    Today
     Recursion definition
     Recursion examples and how to evaluate O()
    of a recursion
     Linear recursion
     Binary recursion

     Tail Recursion
     Elimination tail recursive

    4
    What is Recursion?

    The Recursion Pattern

    5
    Java implementation

    6
    Content of a Recursive Method

    7
    Visualizing Recursion

    8
    Today
     Recursion definition
     Recursion examples and how to evaluate O()
    of a recursion
     Linear recursion
     Binary recursion

     Tail Recursion
     Elimination tail recursive

    9
    Linear Recursion

    10
    Example of Linear Recursion

    11
    Example: Reversing an Array

    12
    Example: Reversing an Array (1)

    13
    Example: Reversing an Array (2)

    4 3 1 8 2 4 7 5

    14
    Defining Arguments for Recursion

    15
    Example: Computing Powers

    16
    Example: Computing Powers

    17
    Recursive Squaring

    18
    Recursive Squaring (cont’d)

    19
    Recursive Squaring Method

    20
    Analysis

    21
    Recursive trace of computing Power (2,13)

    22
    Today
     Recursion definition
     Recursion examples and how to evaluate O()
    of a recursion
     Linear recursion
     Binary recursion

     Tail Recursion
     Elimination tail recursive

    23
    Binary Recursion

    24
    Example: Summing Array Elements

    1 O(log n )

    depth of recursion: 1+log2n

    25
    Concrete Example: Summing Array
    Elements

    26
    Example: Summing Array Elements

    27
    Example: Summing Array Elements
    Note

    28
    Example: Fibonacci Numbers

    29
    Example: Fibonacci Numbers

    30
    Example: Fibonacci Numbers

    Terribly
    inefficient!

    31
    Example: Fibonacci Numbers

    32
    A Better Fibonacci Algorithm

    33
    A Better Fibonacci Program

    34
    Today
     Recursion definition
     Recursion examples and how to evaluate O()
    of a recursion
     Linear recursion
     Binary recursion

     Tail Recursion
     Elimination tail recursive

    35
    Tail Recursion

    36
    Tail Recursion Example

    Iterative Program

    37
    Not Tail Recursion Example

    38
    Today
     Recursion definition
     Recursion examples and how to evaluate O()
    of a recursion
     Linear recursion
     Binary recursion

     Tail Recursion
     Elimination tail recursive

    39
    References
    These slides has been extracted, modified and updated from
    original slides of :
    1. Data Structures and Algorithms in Java, 6th edition. John
    Wiley& Sons,
    2. Java Software Structures, 4th Edition, Lewis/Chase, 2014

    Copyright © Wiley, Michael T. Goodrich, Roberto TamassiaCopyright © 2014


    Copyright © Lewis/Chase, 2014
    Copyright © 2015 Nancy Acemian
    Copyright © 2015 Nora Houari
    All rights reserved

    40

    You might also like