Mastering Recursion in Racket: A Step-by-Step Lab Guide for CSCI 301

Introduction: Why Recursion Matters in Racket

Recursion is the backbone of functional programming, and Racket (a dialect of Scheme) makes it elegant. In this tutorial, we'll break down the key exercises from CSCI 301 Lab 2, helping you master recursion without copying solutions. Whether you're coding a recursive function to generate a list or debug a mysterious function, these skills are essential for your programming toolkit. Let's dive in with a timely analogy: think of recursion like a viral TikTok challenge—each step builds on the previous one until you reach a base case (the final video).

1. Understanding the Mystery Function

What Does (mystery '(1 2 3)) Return?

Load the function:

(define (mystery L) (if (null? L) L (append (mystery (cdr L)) (list (car L)))))

Run (mystery '(1 2 3)). The result is (3 2 1). The function reverses the list! How? It recursively processes the tail (cdr L), then appends the head (car L) as a single-element list at the end. For (mystery '((1 2) (3 4) 5 6)), you get (6 5 (3 4) (1 2)). The function reverses the top-level list, preserving sublists as elements.

How Does the Return Value Work Without a Return Statement?

In Racket, every expression evaluates to a value. The if expression returns either the consequent (when condition is true) or the alternative (when false). The function's body is a single expression, so its value becomes the function's return. No explicit return needed—the last evaluated expression is the result.

2. Debugging with DrRacket: Step Through Recursion

Click the Debug button and run (mystery '(1 2 3)). Use Step to watch the green arrow move through code. The gray bar shows return values. Hover over L to see its current value. The stack trace on the right shows nested calls. This is like watching a recursive function unfold in slow motion—perfect for understanding how each call builds toward the final result.

3. Adding Output: The Role of begin and displayln

Modify the function:

(define (mystery L) (if (null? L) L (begin (displayln L) (append (mystery (cdr L)) (list (car L))))))

begin sequences multiple expressions; it evaluates them in order and returns the last one's value. displayln prints its argument followed by a newline, but returns #<void>. So begin allows you to print before computing the recursive call. Run it and see each recursive call's L printed.

4. Write gen-list: Generate a List of Consecutive Integers

Define a recursive function that builds a list from start to end. Base case: if start > end, return empty list. Otherwise, cons start onto the result of (gen-list (+ start 1) end).

(define (gen-list start end) (if (> start end) '() (cons start (gen-list (+ start 1) end))))

Test: (gen-list 1 5) → (1 2 3 4 5).

5. Write sum: Add Up All Elements in a List

Recursively add the first element to the sum of the rest. Base case: empty list returns 0.

(define (sum lst) (if (null? lst) 0 (+ (car lst) (sum (cdr lst)))))

Test: (sum '(4 5 0 1)) → 10; (sum (gen-list 1 5)) → 15.

6. Write retrieve-first-n: Return First n Elements

Return the first n elements of a list. Handle edge cases: if n <= 0, return empty; if n >= length, return the whole list.

(define (retrieve-first-n n lst) (cond ((<= n 0) '()) ((null? lst) '()) (else (cons (car lst) (retrieve-first-n (- n 1) (cdr lst))))))

Test: (retrieve-first-n 3 '(a b c d e f g h i)) → (a b c).

7. Write pair-sum?: Check Adjacent Pairs Sum to a Value

Check if any two adjacent elements sum to val. Base cases: if list has fewer than 2 elements, return #f. Otherwise, check if (+ (car lst) (cadr lst)) equals val; if yes, return #t; else recurse on (cdr lst).

(define (pair-sum? lst val) (cond ((< (length lst) 2) #f) ((= (+ (car lst) (cadr lst)) val) #t) (else (pair-sum? (cdr lst) val))))

Test: (pair-sum? '(1 2 3) 3) → #t; (pair-sum? (gen-list 1 100) 1000) → #f.

Conclusion: Recursion as a Superpower

Recursion in Racket is like a chain reaction: each call reduces the problem until a base case stops it. By writing gen-list, sum, retrieve-first-n, and pair-sum?, you've practiced the core pattern. Remember to use the debugger to visualize recursion—it's your best friend. Now go ace that lab!