#lang racket

(require csc151)
(require racket/match)
(require racket/undefined)
(require rackunit)

;; CSC 151-01 (Spring 2021, Term 1)
;; Lab: Numeric recursion (Side B)
;;   https://rebelsky.cs.grinnell.edu/Courses/CSC151/2021SpT1/code/labs/numeric-recursion
;; Authors: YOUR NAMES HERE
;; Date: THE DATE HERE
;; Acknowledgements:
;;   ACKNOWLEDGEMENTS HERE

#|
In this lab, we'll continue practice designing and writing recursive
functions, this time, over the natural numbers.
|#

#| A |#

; +-------------------------+----------------------------------------
; | Exercise 1: Replicators |
; +-------------------------+

#| B |#

; +---------------------------+--------------------------------------
; | Exercise 2: Counting down |
; +---------------------------+

#|
Complete the definition of `(count-down n)` below that takes a
natural number `n` and returns a list that contains the numbers
starting with `n` going down to 1.  For example

> (count-down 5)
'(5 4 3 2 1)

**You must use recursion to accomplish this task.**

You should also write appropriate documentation and a set of RackUnit
tests for this procedure to ensure that it is correct.
|#

;;; (count-down n) ->
;;;   n :
;;;
(define count-down
  (lambda (n)
    undefined))

; +---------------------------------+--------------------------------
; | Exercise 3: Flipping the script |
; +---------------------------------+

#|
The `count-down` function you just implemented is suspiciously close
to the `range` function we use to generate a sequence of numbers in
the range 1 to n. For ease of implementation, we'll consider range to
be *inclusive* on n rather than *exclusive*. It will be relatively
easy to change our final result so that our function after the fact.

Here is a bad implementation of range likely using the same technique
that you used for `count-down`:
|#

;;; (bad-range n) -> listof integer?
;;;   n : non-negative-integer?
;;; Construct a list of all the values from 1 through n, inclusive.
(define bad-range
  (lambda (n)
    (if (zero? n)
        null
        (cons n (bad-range (- n 1))))))

#|
a. Experiment with this function on a few inputs. In a sentence or
two below, describe the problem with this function and why this is the
case.

<TODO: describe the problem you encountered here>
|#

#|
b. There's a few ways of fixing this function. We could run bad-range
and reverse the input, but that requires us to "traverse" the list
twice---once to create the list and once to reverse it. Instead, we'll
use this opportunity to introduce a new recursion technique, the
*accumulator*. Rather than returning an "empty" value in the base
case, we use an *extra argument* to our recursive function that serves
to accumulate the results at each step of the recursion. We then
return this accumlator when we done processing the recursive
structure.

Complete the definition of `(acc-range n so-far)` which takes a
natural number `n` and a list of values created `so-far` and
recursively prepends the numbers n to 1 (inclusive), in order, onto
the front of `so-far`, resulting in a list that begins with the
numbers 1 through n.

**You may not use `range` or `append` to complete this procedure!  You
should be able to complete the procedure using `cons` and appropriate
recursive calls to `acc-range`.**

Here are some examples of `acc-range`'s execution:

> (acc-range 5 (list 8 10 12))
'(1 2 3 4 5 8 10 12)
> (acc-range 0 (list 4 1 2))
'(4 1 2)
> (acc-range 3 (list 3 2 1))
'(1 2 3 3 2 1)
> (acc-range 3 (list 4 5 6))
'(1 2 3 4 5 6)

> (acc-range 4 '())
'(1 2 3 4)
> (acc-range 3 '(4))
'(1 2 3 4)
> (acc-range 2 '(3 4))
'(1 2 3 4)
> (acc-range 1 '(2 3 4))
'(1 2 3 4)
> (acc-range 0 '(1 2 3 4))
'(1 2 3 4)

Don't forget to write appropriate documentation and a set of RackUnit
tests for this function!
|#

;;; (acc-range n so-far) ->
;;;   n : 
;;;   so-far : 
;;; 
(define acc-range
  (lambda (n so-far)
    undefined))

#|
c. Use `acc-range` to implement `(good-range n)` which correctly
produces a list of the numbers 0 through n, inclusive. 

Don't forget to write appropriate documentation and a set of rackunit
tests for this procedure.
|#

;;; (good-range n) -> 
;;;   n :
;;;
(define good-range
  (lambda (n)
    (acc-range n undefined)))

#| A |#

; +---------------------------+--------------------------------------
; | Exercise 4: Powers of ... |
; +---------------------------+

#| B |#

; +---------------------+--------------------------------------------
; | Exercise 5: Fibbing |
; +---------------------+

#|
The Fibonacci sequence (https://oeis.org/A000045) is a classic
numeric sequence in mathematics. It is defined recursively as follows:

fib(0) = 0
fib(1) = 1
fib(n) = fib(n-1) + fib(n-2)
|#

#|
a. Complete the definition of `(naive-fib n)` below directly
translating its recursive definition into code. Write an appropriate
doc comment and set of rackunit tests to ensure its correctness.
|#

;;; (naive-fib n) : non-negative-integer?
;;;   n : non-negative-integer?
;;; Compute the nth number in the Fibonacci sequence, defined in
;;; traditionally mathematical notation as
;;;   fib(0) = 0
;;;   fib(1) = 1
;;;   fib(n) = fib(n-1) + fib(n-2)
(define naive-fib
  (lambda (n)
    undefined))

#|
b. Try out `naive-fib` on a variety of inputs, including
reasonably-sized inputs such as in the 20s, 30s, and upwards.  You
should notice that the function starts taking a long to execute as you
go up in numbers.  Remember that you can use `(time exp)` to find out
how long it takes Racket to compute something.  Record a few times
here.

<TODO: Continue filling in the data below.>
> (time (naive-fib 20))
...

|#

#|
c. Use your mental model of computation to sketch out how naive-fib
executes on a small input, say 5. Notice the pattern of function
calls. In a few sentences below, describe what you observed and use
your findings to speculate why `naive-fib` is so slow on these
seemingly reasonable inputs.

<TODO: write your explanation here>
|#

#|
d. Optionally, propose a mechanism or mechanisms you might use to
make `naive-fib` more efficient.

<TODO: write your suggestion here>
|#