# 06 - Recursion

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

A function that calls itself during execution

A function that calls another function from within itself

A function that uses a recursive call to call other functions

A function that repeats itself indefinitely

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 5

Line 3

This is not a recursive function

Line 2

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

1

4

6

5

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 a base case of 4 but this is met on the first call so causes an error

The function asks for 'n' but it is called in line 5 with the number '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

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

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

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

3

5

1

6

7. The following recursive function will result in an error. Why?
```def recursive_function(n):
if n==5:
return 1
else:
return recursive_function(n+1)

print(recursive_function(6))```

Because line 5 does not decrement down to the base case

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.

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!

Function 2

Function 1

Neither of them are recursive!

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

Recursive functions can be too quick!

There are no disadvantages. Recursion rules!

Recursive functions use a queue for implementation which is time consuming

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

repeat themselves until they run out of memory

call other functions from within themselves

call themselves to solve smaller subproblems

use a while loop to solve a bigger problem