Preview

06 - Recursion

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

  A function that uses a recursive call to call other functions

  A function that repeats itself indefinitely

  A function that calls another function from within itself

  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))

  5

  4

  1

  6

 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)

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

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

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

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

 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 2 should be --> if n==5:

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

  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))

  5

  1

  6

  3

 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 line 2 needs, in this case, to be greater than 6 or it will not work.

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

  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)

  Neither of them are recursive!

  Both 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:

  it will often throw a StackOverflowException if processing big sets

  There are no disadvantages. Recursion rules!

  Recursive functions use a queue for implementation which is time consuming

  Recursive functions can be too quick!

 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 themselves to solve smaller subproblems

  repeat themselves until they run out of memory

  use a while loop to solve a bigger problem

  call other functions from within themselves


Report an error