recursionlispracketracket-student-languages# How to optimize runtime on recursive Racket function to determine maximum of element in list?

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,

Solution

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.

- Python - count the number of prime divisors without using range
- Is it bad practice to use Recursion where it isn't necessary?
- How to Avoid Duplicates and Non-Existent Paths When Using Recursion?
- Parenthesis representation of BinTree to BinTree
- Create SQLite View From Two Tables Recursively
- Template excessive recursion at instantiation cuda
- How do I read what's in a binary tree in Haskell?
- In PHP, how to recurse through a Closure when the variable name holding the anonymous function is a variable-variable
- Is there any way to catch and handle infinite recursive functions that create Tkinter windows?
- JavaFx sorting visualiser
- "Palindrome recursive function" detects palindromes right but doesn't behave as expected
- Why does console.log report the value of my variable, but return doesn't?
- How do increment and decrement work with recursion
- Windows Batch File Looping Through Directories to Process Files?
- Find the maximum number of pieces a rod can be cut
- Overflow while attempting to calculate the Hamming weight in C++
- How to tidying my Java code because it has too many looping
- Does PHPUnit have some inbuilt recursive array comparison function?
- Optimization of tail recursion in R
- Using Recursion in C#
- Way to go from recursion to iteration
- Inconsistent error behaviour on recursive Typescript type
- Recursive type not working with optional properties
- recursive .bat file to apply jpegtran and pngout to all images in subfolders
- Why don't functions recurse as many times as the limit I set with sys.setrecursionlimit()?
- trace a nested recursion in Ocaml
- Very slow recursive type
- how --x works fine in this code but x-- gets StackOverflowError
- Recursion function in Python
- Recursion - Not Returning Values as Expected