here is my wonderful & working LISP racket "intermediate with lambda" style recursive function to determine the symbol with the highest value of symbols in a list.
(define maximum
(lambda [x]
(cond
[(empty? x) 0]
[(cons? x)
(cond
[(>= (first x) (maximum (rest x))) (first x)]
[else (maximum (rest x))]
)
]
)
)
)
(check-expect (maximum '(1 2 3)) 3)
(check-expect (maximum '(1)) 1)
(check-expect (maximum '(0)) 0)
How can I check for and optimize runtime?
Is recursion any different in runtime than iteration?
Thank you for your answer!
Kind regards,
There is one main thing that will improve the performance greatly, taking it from exponential to linear time.
Don't re-compute the recursion, save it as an intermediate result.
In the inner cond expression, (maximum (rest x)) is computed twice. Once in the question of the first branch, and once is the answer of the second branch.
(cond
[(>= (first x) (maximum (rest x))) (first x)]
[else (maximum (rest x))])
In the common case where the first question is false, (maximum (rest x)) will be re-computed, doubling the work it has to do. Even worse, this doubling can potentially happen at every level of recursion in the worst case when the max is at the end. This is what makes it exponential.
To fix this, you can use local to define and name the intermediate result.
(local [(define maxrst (maximum (rest x)))]
(cond
[(>= (first x) maxrst) (first x)]
[else maxrst]))
This takes the big-O complexity from exponential to linear in the length of the input.
There are other potential optimizations such as taking advantage of tail-calls, but those aren't as important as saving the intermediate result to avoid re-computing the recursion.
This method of improving performance using local definitions is also described in How to Design Programs 2e Figure 100: Using local to improve performance.