#lang racket

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

;; CSC 151-01 (Fall 2021)
;; Lab: 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 |
; +-------------------------+

#|
Consider the definition of `(replicate n v)` below that takes a
natural number `n` and returns a list that contains `n` copies of `v`.
|#

;;; (replicate n v)
;;;   n : 
;;;   v :
;;;
(define replicate
  (lambda (n v)
    (if (zero? n)
        null
        (cons v (replicate (- n 1) v)))))

#|
Fill in the following information for replicate.

base-case-test: <TODO: fill in>

base-case-value: <TODO: fill in>

parameter simplification: <TODO: fill in>

recursive call: <TODO: fill in>

post-recursion step: <TODO: fill in>
|#

#| 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 ... |
; +---------------------------+

#|
a. Write a recursive procedure, `(powers-of-two n)`, that produces a 
list of all of the powers of two less than or equal to n.

    > (powers-of-two 5)
    '(1 2 4)
    > (powers-of-two 8)
    '(1 2 4 8)
    > (powers-of-two 10)
    '(1 2 4 8)
    > (powers-of-two 100)
    '(1 2 4 8 16 32 64)

Hint: You may want to write a helper procedure that takes an extra
parameter.
|#

;;; (powers-of-two n) ->
;;;   n :
;;;
(define powers-of-two
  (lambda (n)
    undefined))

#|
b. Write a procedure, (powers-of-three n), that produces a list of
all of the powers of three less than or equal to n.

    > (powers-of-three 100)
    '(1 3 9 27 81)
    > (powers-of-three 1000)
    '(1 3 9 27 81 243 729)
|#

;;; (powers-of-three n) ->
;;;   n :
;;;
(define powers-of-three
  (lambda (n)
    undefined))

#|
c. You’ve likely found that powers-of-two and powers-of-three look
remarkably the same. When you find procedures that look the same,
one approach is to write a template that you can copy and paste. But 
a better strategy is to add an extra parameter.

Write a procedure, (powers-of k n), that produces a list of all the
powers of k less than or equal to n.

    > (powers-of 2 100)
    '(1 2 4 8 16 32 64)
    > (powers-of 3 100)
    '(1 3 9 27 81)
    > (powers-of pi 100)
    '(1 3.141592653589793 9.869604401089358 31.006276680299816 97.40909103400242)
|#

;;; (powers-of k n) ->
;;;   k :
;;;   n :
;;;
(define powers-of
  (lambda (k n)
    undefined))

#|
d. Rewrite powers-of-two and powers-of-three in terms of powers-of.

Note: If possible, use `section` rather than `lambda`.
|#

(define new-powers-of-two 
  undefined)

(define new-powers-of-three
  undefined)

#| B |#

; +-------------------------------+----------------------------------
; | Exercise 5: Sums of Fractions |
; +-------------------------------+

#|
Consider the sum 1/1 + 1/2 + 1/3 + ... + 1/n.  While there may be
a formula that some mathematicians know for that sum, it may also
be easier to just have the computer calculate it for us.

Finish writing the procedure, `(fractional-sum n)`, below, which
computes that sum.

Hint: You may find it easier to think of the sum as 
  1/n + 1/(n-1) + ... + 1/3 + 1/2 + 1/1.
Or, in Scheme notation
  (+ (/ 1 n) (+ (/ 1 (- n 1)) ... (+ (/ 1 3) (+ (/ 1 2) (/ 1 1)))))
|#

;;; (fractional-sum n) -> rational?
;;;   n : positive-integer?
;;; Computes 1/1 + 1/2 + 1/3 + ... + 1/n.
(define fractional-sum
  (lambda (n)
    undefined))

#|
(test-equal? "(fractional-sum 1)" (fractional-sum 1) 1)
(test-equal? "(fractional-sum 2)" (fractional-sum 2) (+ 1 1/2))
(test-equal? "(fractional-sum 3)" (fractional-sum 3) (+ 1 1/2 1/3))
(test-equal? "(fractional-sum 4)" (fractional-sum 4) (+ 1 1/2 1/3 1/4))
(test-equal? "(fractional-sum 5)" (fractional-sum 5) (+ 1 1/2 1/3 1/4 1/5))
|#

#| AB |#

; +---------------------------+--------------------------------------
; | For those with extra time |
; +---------------------------+

#|
If you find that you have extra time and want to further explore some
of these issues, consider implementing any of the following procedures.
|#

; +------------------+-----------------------------------------------
; | Extra 1: 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>
|#

; +-----------------------+------------------------------------------
; | Extra 2: More Fibbing |
; +-----------------------+

#|
One approach to the Fibonacci problem is to pass along *three* accumulators,
one for where we are in the sequence, one for the current Fibonacci number,
and one for the prior Fibonacci number.
|#

;;; (fibonacci-helper n k fib-k fib-k-1)
;;;   n : positive integer?
;;;   k : positive integer?
;;;   fib-k : non-negative integer?
;;;   fib-k-1 : non-negative integer?
;;; Compute the nth Fibonacci number given the kth and kth-1st
;;; Fibonacci numbers.
(define fibonacci-helper 
  (lambda (n k fib-k fib-k-1)
    undefined))

(define fibonacci
  (lambda (n)
    (fibonacci-helper n 1 1 0)))

#|
Complete the definition above.
|#