Beginner: A good base case for recursion?

Hi there!

I'm having trouble figuring out what would constitute a good stopping condition in this exercise where a function consumes a ListOfSchools and produces a School...

When such functions deal with numbers, I have no problem finding a good base case... But here?...

Or at least that's what I think the problem is...

Any hints on how to develop a better "mental image" of what a good stopping condition should be in general? Not just with numbers...

Thank you in advance for any help!

Here's my exercise bellow. My question is about the question (C), and the corresponding function I called 'lowest-tui'

(require 2htdp/image)
;; tuition-graph-starter.rkt  (just the problem statements)

; 
; PROBLEM:
; 
; Eva is trying to decide where to go to university. One important factor for her is 
; tuition costs. Eva is a visual thinker, and has taken Systematic Program Design, 
; so she decides to design a program that will help her visualize the costs at 
; different schools. She decides to start simply, knowing she can revise her design
; later.
; 
; The information she has so far is the names of some schools as well as their 
; international student tuition costs. She would like to be able to represent that
; information in bar charts like this one:
; 
; 
;         .
;         
; (A) Design data definitions to represent the information Eva has.
; (B) Design a function that consumes information about schools and their
;     tuition and produces a bar chart.
; (C) Design a function that consumes information about schools and produces
;     the school with the lowest international student tuition.
; 


; DOMAIN ANALYSIS:
; ================
; 
; 
; CONSTANT INFORMATION:
; =====================
; - Bar color
; - Bar width
; - text font size
; - text color
; - Y-scale
; 
; CHANGING INFORMATION:
; =====================
; -Number of bars
; -Bar height
; -School names
; -Number of schools
; 
; ===
; !NO BIG-BANG OPTION!



;; CONSTANTS:
;;===========

(define BAR-COLOR "lightblue")
(define BAR-WIDTH 50)
(define FONT-SIZE 25)
(define FONT-COLOR "black")
(define Y-SCALE 1/30)

;; DATA DEFINITIONS:
;;==================

;; (@htdd school)

(define-struct school (name tuition))

;; School is (make-school String Natural)
;; Interp. A school with:
;;  - name as the school's name
;;  - tuition as student's tuition in USD

(define S1 (make-school "Lemsid" 5800))       ; School named Lemsid, with a tuition of 5800 USD
(define S2 (make-school "Ellissi" 4500))      ; School named Ellissi, with a tuition of 4500 USD
(define S3 (make-school "Abd ElMoumen" 7800)) ; School named Abd ElMoumen with a tuition of 7800 USD

#;
(define (fn-for-school s)
  (... (school-name s)      ; String
       (school-tuition s))) ; Natural

;; Templates rules used:
;;  - compound: 2 fields

;;===

;; (@htdd ListOfSchool)

;; ListOfSchool is one of:
;;  - empty
;;  - (cons School ListOfSchool)
;; Interp. A list of schools

(define LOS1 empty)
(define LOS2 S1)
(define LOS3 (cons S1
                   (cons S2
                         (cons S3
                               empty))))
#;
(define (fn-for-los los)
  (cond [(empty? los) (...)]
        [else
         (... (fn-for-school (first los))
              (fn-for-los (rest los)))]))

;; Template rules used:
;;  - one of 2 cases
;;   - atomic distict: empty
;;   - compound: 2 fields
;;    - reference (first los) is School
;;    - self-reference: (rest los) is ListOfSchool

;;===

;; FUNCTIONS:
;;===========

;; (@htdf barchart)
;; (@Signature: ListOfSchool -> Image)
;; Produces a bar chart of a given list of schools and their respective tuitions.
(check-expect (barchart empty)
              (square 0 "solid" "white"))

(check-expect (barchart (cons S1
                              (cons S2 empty)))
              (beside/align "bottom"
                            (overlay/align "center" "bottom"
                                           (rectangle BAR-WIDTH
                                                      (* 5800 Y-SCALE) "outline" "pink")
                                           (rotate 90 (text "Lemsid" FONT-SIZE FONT-COLOR))
                                           (rectangle BAR-WIDTH
                                                      (* 5800 Y-SCALE) "solid" BAR-COLOR))
                            (overlay/align "center" "bottom"
                                           (rectangle BAR-WIDTH
                                                      (* 4500 Y-SCALE) "outline" "pink")
                                           (rotate 90 (text "Ellissi" FONT-SIZE FONT-COLOR))
                                           (rectangle BAR-WIDTH
                                                      (* 4500 Y-SCALE) "solid" BAR-COLOR))))
                             
;; (define (barchart los) (square 0 "solid" "white")) ;stub

(define (barchart los)
  (cond [(empty? los) (square 0 "solid" "white")]
        [else
         (beside/align "bottom"
                       (draw-bar (first los))
                       (barchart (rest los)))]))

;;===

;; (@htdf draw-bar)
;; (@Signature: School -> image)
;; Produces an image of a bar for an single school,
;; with a bar height that depends on the cost of the school's tuition
(check-expect (draw-bar S1)
              (overlay/align "center" "bottom"
                             (rectangle BAR-WIDTH
                                        (* 5800 Y-SCALE) "outline" "pink")
                             (rotate 90 (text "Lemsid" FONT-SIZE FONT-COLOR))
                             (rectangle BAR-WIDTH
                                        (* 5800 Y-SCALE) "solid" BAR-COLOR)))
              

;; (define (draw-bar s) (square 0 "solid' 'red")) ; stub

(define (draw-bar s)
  (overlay/align "center" "bottom"
                 (rectangle BAR-WIDTH
                            (* (school-tuition s) Y-SCALE) "outline" "pink")
                 (rotate 90 (text (school-name s) FONT-SIZE FONT-COLOR))
                 (rectangle BAR-WIDTH
                            (* (school-tuition s) Y-SCALE) "solid" BAR-COLOR)))

;;===

;; (@hdtf lowest-tui)
;; (@Signature ListOfSchool -> School)
;; Produces the school with the lowest tuitition in a given list
(check-expect (lowest-tui empty)
              (make-school "" 0))
(check-expect (lowest-tui LOS3)
              S2)

;; (define (lowest-tui s) S1) ; stub

(define (lowest-tui los)
  (cond [(empty? los) (make-school "" 0)]
        [else
         (if (< (school-tuition (first los)) (school-tuition (lowest-tui (rest los))))
             (first los)
             (lowest-tui (rest los)))]))

;; (barchart LOS3)
1 Like

The base case is probably the empty school list. I didn't read your code, but I hope this helps:

#lang racket

(define all-the-schools '(a b c d e))

(let loop ([schools all-the-schools])
  (displayln (list "There are" (length schools) "in the list"))
  (if (null? schools)
      (displayln "That's all folks")
      (begin
        (displayln (list "The current schools is" (car schools)))
        (newline)
        (loop (cdr schools)))))
2 Likes

Hi @gus-massa !

I've only reached the 4th module in the edx course (there are 9 in total), and I haven't yet encountered the 'let' or 'loop' terms...

So thank you for the answer, but I'm afraid I'm not able to benefit from it at this stage.

Since I posted this question, I remembered these exercises come with a version that has the solution, but I didn't get that one either.

Here's what the version with the solution says about this case anyway:

;; ListOfSchool -> School
;; produce the school with the lowest tuition
;; ASSUME the list includes at least one school or else
;;        the notion of cheapest doesn't make sense

I have then come to accept that I'll not be able to get all the exercises right, that it's normal to struggle with a small portion of them, and that this shouldn't stop me from continuing with the lessons.

But thanks again! :slight_smile:

Cheers!

;; ASSUME the list includes at least one school or else
;; the notion of cheapest doesn't make sense

This means the base case is the list of one school.

In most list functions, the base case is the empty list.
The predicate for the empty list is empty?.

We need a function that tests whether the list has one element.

This version

(define (length1? xs)
   (= (length xs) 1))

sort of works - but for a long list, the call (length xs) will take time proportional to the length of the list.

Instead we can use:

(define (length1? xs)
    (and (not (empty? xs))
             (empty? (rest xs))))

Now you can use (length1? los) as your base case.
If you have a list of only one school, then that one school is the cheapest.

1 Like

IFIRC, function length has amortisized time O(1).

Hi there, nice people of Racket!

I thank you for all of your answers, but I have to say they mostly went waaay over my head, as this was more of a Beginning Student Language question, than it was an "actual Racket" question...

I did end up making a function that works... And it was the 'check-expect' test for the base case (in the solution file) that made it click for me.

It looked like this:

(check-expect (cheapest? (cons S1 empty))
              S1)

So my function is a bit different than the one given by the course, but it does work, and I'm so happy! :grin:

Here it is:

(define (lowest-tui los)
  (cond [(empty? (rest los)) (first los)]
        [else
         (if (< (school-tuition (first los))
                (school-tuition (lowest-tui (rest los))))
             (first los)
             (lowest-tui (rest los)))]))

Thanks again to all of you for your time! :+1:

2 Likes

About named-lets: I notice it a few hour later. I should have used a definition. Also, because the recursion is more clear.

I think you already solved the original problem, but just in case it's useful for someone in the future:

#lang racket

(define all-the-schools '(a b c d e))

(define (f schools)
  (displayln (list "There are" (length schools) "in the list"))
  (if (null? schools)
      (displayln "That's all folks")
      (begin
        (displayln (list "The current schools is" (car schools)))
        (newline)
        (f (cdr schools)))))

(f all-the-schools)

(I renamed loop to f, because it looks nicer.)

length is not amortized or constant time. You're probably thinking of the list? function.

Your solution looks exactly right. It doesn't look like anyone here has drawn your attention to section 9.2 of the (free online) How To Design Programs text (on which I believe the EdX course may be based), which is all about non-empty lists, and how in that case the base case should be a list of length one, rather than of length zero:

http://htdp.org/2022-8-7/Book/part_two.html#(part._sec~3alists~3ane)

The TL;DR here is that you got it exactly right.

2 Likes

Just a quick question unrelated to the problem: What edx course are you referring to? I couldn't find a racket course there.

Most likely one of Gregor Kiczales courses.

https://www.edx.org/bio/gregor-kiczales

https://edge.edx.org/courses/course-v1:UBC+CPSC110+2021W2/77860a93562d40bda45e452ea064998b/

2 Likes

Hi @jbclements !

Thank you for your encouraging words, much appreciated! :slight_smile:

I actually started by buying the physical Htdp book, and followed it until the Enumerations chapter. But then I came across the edx video series, and as a non-native english speaker, I thought it'd be more accessible and more fluid for me to follow along, while someone shows how it's done on the screen.

So I guess I'll finish the video series first, and then go back to the book. It's likely that the explanations are more rigorous and complete in written form.

As for the chapter you provided the link for, it is not too long, and I will read it! :+1:

Thanks again!

The video series is twofold: The first part is called "How To Code Simple Data", and the second one "How To Code Complex Data".

I just hope they haven't omitted important parts of the book.

@soegaard Yes, Gregor Kiczales... That's the professor who does the video series.