Preview

06 - Recursion

 1. What is the best definition of a recursive function?

  A function that repeats itself indefinitely

  A function that calls another function from within itself

  A function that uses a recursive call to call other functions

  A function that calls itself during execution

 2. On what line is the 'recursive call' taking place in the following code?
def mystery(n):
    if n == 1:
        return 1
    else:
        return n + mystery(n-1)


print(mystery(3))

  Line 2

  Line 3

  This is not a recursive function

  Line 5

 3. Can you trace the output of the following recursive function? What number is returned?
def mystery(n):
    if n == 1:
        return 1
    else:
        return n + mystery(n-1)


print(mystery(3))

  6

  1

  5

  4

 4. The following function 'moose', when run, results in a "Maximum call stack size" error. Can you explain why?
def moose(n):
        return n + moose(n)

moose(4)

  There is no base case or stopping condition so it goes on forever

  The function is not a recursive function, so runs out of memory

  The function asks for 'n' but it is called in line 5 with the number '4'

  There is a base case of 4 but this is met on the first call so causes an error

 5. Running this function will cause an error. What needs fixing?
def moose(n):
    if n==1: #the base case needs to be 1, as it is going down by 1
        return 1
    else:
        return n + moose(n+1) 

print(moose(5))

  Line 5 should be --> return n - moose(n+1)

  Line 5 should be --> return n + moose(n-1)

  Line 2 should be --> if n==5:

  Line 2 should be --> if n<0:

 6. What is the output of this function?
def recursive_function(n):
    if n==5:
        return 1
    else:
        return recursive_function(n+1)

print(recursive_function(3))

  6

  5

  3

  1

 7. The following recursive function will fail to run. Why?
def recursive_function(n):
    if n==5:
        return 1
    else:
        return recursive_function(n+1)

print(recursive_function(6))

  Because the base case on line 2 will never be met.

  Because line 2 needs, in this case, to be greater than 6 or it will not work.

  Because line 5 does not decrement down to the base case

  All these options are valid

 8. Note the two functions for the Fibonacci sequence below. Which one is recursive?
#function 1
def fibi(n):
    a, b = 0, 1
    for i in range(n):
        a, b = b, a + b
    return a


#function 2
def fib(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        return fib(n-1) + fib(n-2)

  Both are recursive!

  Neither of them are recursive!

  Function 1

  Function 2

 9. Recursion is very beneficial when the iterative solutions requires that you simulate recursion with a stack. Recursion acknowledges that the compiler already manages a stack to accomplish precisely what you need. A disadvantage of recursion is:

  Recursive functions can be too quick!

  Recursive functions use a queue for implementation which is time consuming

  it will often throw a StackOverflowException if processing big sets

  There are no disadvantages. Recursion rules!

 10. Recursion could mean redefining something in terms of itself usually at some smaller scale, perhaps multiple times, to achieve your objective. Think of it like this: Recursive functions can ...

  call other functions from within themselves

  use a while loop to solve a bigger problem

  repeat themselves until they run out of memory

  call themselves to solve smaller subproblems