知识库

CS107-Scheme函数定义讲义

4分钟阅读

title: CS107-第30讲-Scheme函数定义 source: Stanford CS107 Programming Paradigms original_path: /田浩然上传的资料/电子书/ProgrammingParadigms/materials/icsppcs107/30-Scheme-Functions.pdf author: Jerry Cain, Ben Newman, David Hall size: 99KB pages: 11 date_processed: 2026-09-30 method: PDF文本提取 status: done

Scheme函数定义 - Stanford CS107讲义

核心主题

本讲义介绍Scheme编程语言中函数定义的基本语法和递归编程模式。

关键概念

1. define特殊形式

(define (procedure-name <arguments>)
  <expression to evaluate>)

示例：摄氏转华氏温度函数

(define (celsius->fahrenheit celsius)
  (+ (* 1.8 celsius) 32))

2. 谓词函数命名约定

返回布尔值的函数名以?结尾，如：

  • leap-year? - 判断闰年
  • zero? - 判断是否为零

3. 递归是Scheme的核心

Scheme的核心数据结构是列表（list），列表通过归纳定义，因此递归是自然的选择。

尾递归优化：所有Scheme解释器都能将尾递归转换为迭代等价形式。

4. 典型递归示例

阶乘函数

(define (factorial n)
  (if (zero? n) 1
      (* n (factorial (- n 1)))))

注意：Scheme支持任意大整数。

斐波那契函数

(define (fibonacci n)
  (if (< n 2) n
      (+ (fibonacci (- n 1))
         (fibonacci (- n 2)))))

传统实现效率低（指数级递归调用）。

5. 快速斐波那契（动态规划）

(define (fast-fibonacci n)
  (fast-fibonacci-helper n 0 1))
 
(define (fast-fibonacci-helper n base-0 base-1)
  (cond ((zero? n) base-0)
        ((zero? (- n 1)) base-1)
        (else (fast-fibonacci-helper (- n 1) base-1 (+ base-0 base-1)))))

线性递归而非二叉递归，速度与阶乘相当。

6. car-cdr递归模式

处理列表的标准模式：

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

三重列表函数

(define (triple-everything numbers)
  (if (null? numbers) '()
      (cons (* 3 (car numbers)) 
            (triple-everything (cdr numbers)))))

字符串部分连接

(define (generate-concatenations strings)
  (generate-concatenations-using strings ""))
 
(define (generate-concatenations-using strings accum)
  (if (null? strings) '()
      (cons (string-append accum (car strings))
            (generate-concatenations-using (cdr strings)
                (string-append accum (car strings))))))

7. let绑定

用于避免重复计算子表达式：

(define (pwr base exponent)
  (if (zero? exponent) 1
      (let ((root (pwr base (quotient exponent 2))))
        (if (zero? (remainder exponent 2))
            (* root root)
            (* root root base)))))

let语法结构

(let ((<name-1> <expression-1>)
      (<name-2> <expression-2>)
      ...)
  <expression using names 1 through k>)

注意：let绑定的计算顺序不保证，因此<expression-2>不能使用<name-1>。

8. flatten函数

将任意嵌套列表展平为单层列表：

(define (flatten sequence)
  (cond ((null? sequence) '())
        ((list? (car sequence)) 
         (append (flatten (car sequence))
                 (flatten (cdr sequence))))
        (else (cons (car sequence) 
                    (flatten (cdr sequence))))))

9. 快排实现

分区函数

(define (partition pivot num-list)
  (if (null? num-list) '(() ())
      (let ((split-of-rest (partition pivot (cdr num-list))))
        (if (< (car num-list) pivot)
            (list (cons (car num-list) (car split-of-rest))
                  (cadr split-of-rest))
            (list (car split-of-rest)
                  (cons (car num-list) (car (cdr split-of-rest))))))))

快排函数

(define (quicksort num-list)
  (if (<= (length num-list) 1) num-list
      (let ((split (partition (car num-list) (cdr num-list))))
        (append (quicksort (car split))
                (list (car num-list))
                (quicksort (cadr split))))))

实践要点

  1. 函数文件扩展名：惯例使用.scm
  2. 加载文件：使用(load "filename.scm")
  3. 纯函数式风格：避免副作用，函数组合是核心范式
  4. 列表操作：car取首元素，cdr取剩余列表，cons构建列表，null?判断空列表

知识关联

关系图谱