Scribd Logo
Upload

Welcome to Scribd!

  • 2 views

    1 Wk10 Recursion - Lecture

    Uploaded by

    eddieldavies

    Copyright:

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

    1 Wk10 Recursion - Lecture

    Uploaded by

    eddieldavies
    2 views35 pages

    Original Title

    1 Wk10 recursion_lecture

    Copyright

    © © All Rights Reserved

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    Copyright:

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

    1 Wk10 Recursion - Lecture

    Uploaded by

    eddieldavies

    Copyright:

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

    Recursion

    Dr Rob Blair
    [email protected] SCI 2.19

    1
    Objectives
    decomposition to recursive steps and base cases

    advantages and disadvantages of recursion

    2
    Recursive Function

    defined in terms of base cases and recursive steps

    3
    Base Cases

    return immediately from the function arguments

    4
    Recursive Steps

    call the recursive function

    move arguments closer to the base case

    5
    Factorial

    n!
    6
    Product
    n

    ∏
    n! = n × (n − 1) × …2 × 1 = i
    i=1

    7
    pseudo code

    factorial(n):
    result := 1
    for i := 1 to n
    result := result * i
    return result

    8
    What is the time complexity?

    factorial(n):
    result := 1
    for i := 1 to n
    result := result * i
    return result

    9
    What is the time complexity?

    (n)
    𝒪
    10
    Recurrence

    {n × (n − 1)! if n > 0
    1 if n = 0
    n! =

    11
    pseudo code

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

    12
    base case

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

    13
    base case

    n==0
    14
    we return the result immediately

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

    15
    recursive steps

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

    16
    recursive steps

    all n > 0

    17
    recursive steps

    return n × (n − 1)!

    18
    stack

    19
    factorial(3)

    recursive calls
    pushed to the
    stack

    20
    factorial(2)

    recursive calls
    pushed to the
    stack
    factorial(3)

    21
    factorial(1)

    recursive calls
    pushed to the
    stack factorial(2)

    factorial(3)

    22
    factorial(0)

    recursive calls
    pushed to the factorial(1)
    stack factorial(2)

    factorial(3)

    23
    recursive calls factorial(0)

    pushed to the factorial(1)


    stack factorial(2)

    factorial(3)

    24
    factorial(0)

    factorial(1)

    factorial(2)

    factorial(3)

    25
    factorial(0) base case
    factorial(1) returns a
    factorial(2) value
    factorial(3)

    26
    1 base case
    factorial(1) returns a
    factorial(2) value
    factorial(3)

    27
    1 values are
    factorial(1) popped off
    factorial(2) the stack
    factorial(3)

    28
    1

    values are
    1X1 popped off
    factorial(2) the stack
    factorial(3)

    29
    1X1

    values are
    popped off
    2X1X1 the stack
    factorial(3)

    30
    2X1X1

    values are
    popped off
    the stack
    3X2X1X1

    31
    3X2X1X1

    values are
    popped off
    the stack

    32
    factorial(3) 3X2X1X1
    6

    33
    When should we use
    recursion?
    nice fit for divide and conquer problems
    appropriate for traversing graphs eg: file system
    code can be compact - less code, fewer bugs
    however... rarely the most efficient code

    34
    recursion

    a function that calls itself


    terminates at a base case
    use when appropriate

    35

    You might also like