Recursion in Racket

Our example demonstrates recursive functions in Racket. Here’s a classic factorial implementation:

#lang racket

; This fact function calls itself until it reaches the
; base case of (fact 0).
(define (fact n)
  (if (= n 0)
      1
      (* n (fact (- n 1)))))

(println (fact 7))

; In Racket, we can define recursive functions directly
; without needing to declare them separately.
(define (fib n)
  (if (< n 2)
      n
      (+ (fib (- n 1)) (fib (- n 2)))))

(println (fib 7))

This program defines two recursive functions: fact for calculating factorials and fib for generating Fibonacci numbers.

The fact function demonstrates a simple recursive approach. It calls itself with (- n 1) until it reaches the base case of 0, at which point it returns 1.

In Racket, we can define recursive functions directly without needing to declare them separately, as shown in the fib function. This is different from some other languages where recursive closures might require special syntax or declarations.

The fib function calculates Fibonacci numbers recursively. For any number less than 2, it returns the number itself. For larger numbers, it recursively calls itself with (- n 1) and (- n 2), summing the results.

To run this program, save it to a file (e.g., recursion.rkt) and use the Racket interpreter:

$ racket recursion.rkt
5040
13

The output shows the factorial of 7 (5040) and the 7th Fibonacci number (13).

Racket’s support for recursion makes it easy to implement algorithms that naturally fit a recursive structure, such as tree traversals or divide-and-conquer algorithms.