Recursion in Scheme

Here’s the translated code and explanation in Scheme, formatted in Markdown suitable for Hugo:

Our first example demonstrates a classic factorial function using recursion. Here’s the full source code:

(define (fact n)
  (if (= n 0)
      1
      (* n (fact (- n 1)))))

(display (fact 7))
(newline)

; Recursive procedures can also be defined using lambda
(define fib
  (lambda (n)
    (if (< n 2)
        n
        (+ (fib (- n 1)) (fib (- n 2))))))

(display (fib 7))
(newline)

This fact function calls itself until it reaches the base case of (fact 0).

In Scheme, we can define recursive procedures directly using define, as shown in the fact function. We can also use lambda expressions to create recursive procedures, as demonstrated with the fib function.

To run this program, save it in a file (e.g., recursion.scm) and use your Scheme interpreter. For example, if you’re using Guile:

$ guile recursion.scm
5040
13

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

In Scheme, we don’t need to explicitly declare the type of a function or variable. The language is dynamically typed, so the recursive calls work without any special declarations.

Recursive procedures are a fundamental concept in Scheme and are often used to implement algorithms in a clear and concise manner. The language is designed to optimize tail-recursive calls, making recursion an efficient programming technique in many cases.