尝试在球拍中编写递归函数
Trying to write a recursion function in racket
我正在尝试编写一个常规递归函数和一个尾递归函数，它采用四个参数并计算 ax^2 + b 对于 x 从 q 到 r.
这是我目前所拥有的，但它无法正常工作，我能得到一些关于我的代码有什么问题的信息吗？
(define (sumof a b q r)
(define (sum)
(+ (* (expt q 2) a) b))
(if ( = q r)
0
(+ (+ q 1) (sum))))
调用递归的正确方法如下：
(define (sumof a b q r)
(define (sum q) (+ (* (expt q 2) a) b))
(if (= q r)
0
(+ (sum q)
(sumof a b (+ q 1) r))))
您应该传递在每次迭代时更改的参数，这比从定义环境中捕获它更清晰。并注意 sumof 函数必须如何调用自身进行迭代。作为旁注，您的函数 不是 尾递归。一个合适的尾递归应该是这样的：
(define (sumof a b q r)
(define (sum x) (+ (* a x x) b))
(let loop ((q q) (acc 0))
(if (= q r)
acc
(loop (+ q 1) (+ (sum q) acc)))))
难怪写代码难。虽然递归很有用，但这是介绍它的最糟糕的方法，因为使用递归解决这个问题违背了对良好软件工程实践的任何倾向。
数学规范
查看基本方程式：
很明显问题没有完全说明。是 x < r 还是 x <= r？至少编写规范做出了可能导致 off-by-one 错误明确的假设。
实施
我的意思是我所说的这个问题对健全的软件工程是有害的。有递归的地方。这些地方正是递归使代码更清晰、更容易理解的地方。这是不是其中一个案例。在这种情况下，规范是迭代的，递归地编写实现会增加复杂性和不透明性。
如果我们保持接近规范：
#lang racket
(provide sumof)
(define/contract (sumof a b q r)
(number? number? number? number? . -> . number?)
(define/contract (sigma list-of-numbers f)
((listof number?) (number? . -> . number?) . -> . number?)
(foldl + 0 (map f list-of-numbers)))
;; range will return '() if r + 1 >= q
(define q<=x<=r (range q (add1 r)))
;; a and b are already in lexical scope
(define (ax^2+b x)
(+ (* a x x) b))
;; if the range is empty return zero
;; becuase zero is the identity of addition
(if (pair? q<=x<=r)
(sigma q<=x<=r ax^2+b)
0))
这使用高级运算符 map 和 foldl，当今所有的酷语言都认为它们是猫的叫声。也许是因为它让我们可以写出 (sigma q<=x<=r ax^2+b).
这样的东西
但这是家庭作业
之所以如此糟糕，是因为尾递归的计算机科学是建立在算法的递归描述和迭代描述的特定 class 之间的同构之上的。编程语言的理念是让我们的程序更容易阅读和编写。
尽管根据赋值永远猜不到它 #lang racket 包含一个结构，其目的正是为了明确表达尾递归的同构性和更清楚地编写尾递归算法。
#lang racket
(provide sumof)
(define/contract (sumof a b q r)
(number? number? number? number? . -> . number?)
;; a and b are already in lexical scope
(define (ax^2+b x)
(+ (* a x x) b))
(if (< q r)
(let loop ([x-range (range q (add1 r))]
[sigma 0])
(cond
[(null? x-range) sigma]
[else (loop (rest x-range)
(+ (ax^2+b (first x-range))
sigma))]))
0))
(let loop... 语法清楚地表明尾递归调用实际上是一个循环。
我正在尝试编写一个常规递归函数和一个尾递归函数，它采用四个参数并计算 ax^2 + b 对于 x 从 q 到 r.
这是我目前所拥有的，但它无法正常工作，我能得到一些关于我的代码有什么问题的信息吗？
(define (sumof a b q r)
(define (sum)
(+ (* (expt q 2) a) b))
(if ( = q r)
0
(+ (+ q 1) (sum))))
调用递归的正确方法如下：
(define (sumof a b q r)
(define (sum q) (+ (* (expt q 2) a) b))
(if (= q r)
0
(+ (sum q)
(sumof a b (+ q 1) r))))
您应该传递在每次迭代时更改的参数，这比从定义环境中捕获它更清晰。并注意 sumof 函数必须如何调用自身进行迭代。作为旁注，您的函数 不是 尾递归。一个合适的尾递归应该是这样的：
(define (sumof a b q r)
(define (sum x) (+ (* a x x) b))
(let loop ((q q) (acc 0))
(if (= q r)
acc
(loop (+ q 1) (+ (sum q) acc)))))
难怪写代码难。虽然递归很有用，但这是介绍它的最糟糕的方法，因为使用递归解决这个问题违背了对良好软件工程实践的任何倾向。
数学规范
查看基本方程式：
很明显问题没有完全说明。是 x < r 还是 x <= r？至少编写规范做出了可能导致 off-by-one 错误明确的假设。
实施
我的意思是我所说的这个问题对健全的软件工程是有害的。有递归的地方。这些地方正是递归使代码更清晰、更容易理解的地方。这是不是其中一个案例。在这种情况下，规范是迭代的，递归地编写实现会增加复杂性和不透明性。
如果我们保持接近规范：
#lang racket
(provide sumof)
(define/contract (sumof a b q r)
(number? number? number? number? . -> . number?)
(define/contract (sigma list-of-numbers f)
((listof number?) (number? . -> . number?) . -> . number?)
(foldl + 0 (map f list-of-numbers)))
;; range will return '() if r + 1 >= q
(define q<=x<=r (range q (add1 r)))
;; a and b are already in lexical scope
(define (ax^2+b x)
(+ (* a x x) b))
;; if the range is empty return zero
;; becuase zero is the identity of addition
(if (pair? q<=x<=r)
(sigma q<=x<=r ax^2+b)
0))
这使用高级运算符 map 和 foldl，当今所有的酷语言都认为它们是猫的叫声。也许是因为它让我们可以写出 (sigma q<=x<=r ax^2+b).
但这是家庭作业
之所以如此糟糕，是因为尾递归的计算机科学是建立在算法的递归描述和迭代描述的特定 class 之间的同构之上的。编程语言的理念是让我们的程序更容易阅读和编写。
尽管根据赋值永远猜不到它 #lang racket 包含一个结构，其目的正是为了明确表达尾递归的同构性和更清楚地编写尾递归算法。
#lang racket
(provide sumof)
(define/contract (sumof a b q r)
(number? number? number? number? . -> . number?)
;; a and b are already in lexical scope
(define (ax^2+b x)
(+ (* a x x) b))
(if (< q r)
(let loop ([x-range (range q (add1 r))]
[sigma 0])
(cond
[(null? x-range) sigma]
[else (loop (rest x-range)
(+ (ax^2+b (first x-range))
sigma))]))
0))
(let loop... 语法清楚地表明尾递归调用实际上是一个循环。