;; (guess-recursive lon) guesses that the number sequence lon has a
;; recursive solution and produces the guess.

;; Example:
(check-expect (solution? (guess-recursive '(1 1 2 3 5 8)) '(1 1 2 3 5 8))
              true)
;; guess-recursive: (listof Int) -> (Nat -> Int)
(define (guess-recursive lon)
  (cond [(>= (length lon) 4)
         (local [(define b
                   (cond
                     [(and (= (second lon) 0)
                           (= (third lon) 0)) 0]
                     [(= (- (sqr (second lon))
                            (* (first lon)(third lon))) 0)
                      0]
                     [(= (second lon) 0)
                      (/ (third lon)(first lon))]
                     [else (/ (- (* (fourth lon)(second lon))
                                 (sqr (third lon)))
                              (- (sqr (second lon))
                                 (* (first lon)(third lon))))]))
                 (define a
                   (cond
                     [(and (= (second lon) 0)
                           (= (third lon) 0)) 0]
                     [(= (second lon) 0)
                      (/ (fourth lon)(third lon))]
                     [else (/ (- (third lon)(* b (first lon)))
                              (second lon))]))
                 (define (fib-recursive i)
                   (cond [(= i 0)(first lon)]
                         [(= i 1)(second lon)]
                         [else
                          (local [(define (fast-fib-recursive
                                           i first-num second-num)
                                    (cond [(= i 0) first-num]
                                          [else (fast-fib-recursive
                                                 (sub1 i) second-num
                                                 (+ (* a second-num)
                                                    (* b first-num)))]))]
                            (fast-fib-recursive
                             i (first lon)(second lon)))]))]
           (lambda (x)
             (fib-recursive x)))]
        [else (guess-quadratic lon)]))

;; Tests:
(check-expect (guess-recursive '()) 0)
(check-expect (guess-recursive '(1)) 1)
(check-expect (solution? (guess-recursive '(1 2)) '(1 2)) true)
(check-expect (solution? (guess-recursive '(1 2 3)) '(1 2 3 4 5)) true)
(check-expect (solution? (guess-recursive '(2 4 6 10 16 26)) '(2 4 6 10 16 26))
              true)
(check-expect (solution? (guess-recursive '(1 5 7 17 31 65)) '(1 5 7 17 31 65))
              true)
(check-expect (solution? (guess-recursive '(1 0 3 9 36)) '(1 0 3 9 36 135))
              true)