Best calculator for recurrence relations

[DavidM]

(02-23-2020 07:09 PM)John Keith Wrote:  Neat, but can you do this with SEQ?

Well, it won't win any awards for speed, but the subscripting allowed in symbolic expressions on the 50g does allow a fairly straightforward way to do this. It's not recursive, of course, but this does seem to work for the samples I've tested:

Code:

\<<
   1 R\->I 2. NDUPN \->LIST                  @ build initial result
   \-> max a                                 @ local variables
   \<<
      0.                                     @ placeholder for result
      \<<
         a                                   @ recall current list
         'a(a(n-2))+a(n-a(n-2))' EVAL R\->I  @ obtain next element
         +                                   @ add new element to result
         DUP 'a' STO                         @ update result list
         NIP                                 @ delete previous result
      \>>
      'n' 3. max 1. SEQ                      @ execute SEQuence
   \>>
\>>

Notes:
1) There's no error checking of the input argument (the maximum "n", which must be >2)
2) SEQ wants to build a final list from the results of each iteration of the executable, but in this case the result is simply appended to the existing array for future computations. There's nothing new on the stack for SEQ to encapsulate when it completes, and the stack-based result is not included since it was created before SEQ executes.

It's not particularly elegant, but it works. This could probably be sped up by doing the computations on the stack instead of with a symbolic expression, but the readability would take a significant hit (IMHO).