Recursion - Standard

Question 1

Linear recursion

Answer 1

amount of information stored is dependend linearly on n (size) - creates a chain of defered operations

Question 2

Tree/branching recursion

Answer 2

Like fibonnaci
for very large values of n, large recursive stacks are stored in memory making this type of recursion slow and memory inefficient

Question 3

Tail recursion

Answer 3

recursive call is the last thing that is done before returning
- last call evaluates function’s value
nothing from the higher call eed to be stored
optimised for memory use

Question 4

tail recursive factiorial

Answer 4

facAux 0 r = r
facAu n r = facAux (n-1)(r*n)

facTail n = facAux n 1

Question 5

tail recursive fibonnaci (remember that is Tree recursive)

Answer 5

fibAux n r e s u l t previous
| n == 0 = r e s u l t
| otherwise = fibAux (n − 1) ( r e s u l t + previous ) r e s u l t

f i b T a i l n
| n == 0 = 0
| otherwise = fibAux n 1 0