如何不借助延续性（continuations），用自然递归实现last-non-zero函数？

你的延续性实现利用let/cc直接跳转到最后一个0的位置返回结果，自然递归的思路需要遍历整个列表，通过状态跟踪来决定是否保留当前元素。

实现思路 #

递归遍历列表时，同时跟踪两个状态：

• 已处理好的结果列表
• 是否已经遇到最后一个0（即后续没有更多0）

具体递归逻辑：

1. 列表为空时，返回空列表和#f（表示尚未遇到0）
2. 当前元素是0：
   • 递归处理剩余子列表，得到(处理结果 是否找到最后一个0)
   • 若是否找到最后一个0为#f，说明当前0是最后一个，直接返回(剩余处理结果 #t)（当前0丢弃）
   • 若为#t，说明后面已有最后一个0，当前0需要保留，返回(cons 当前元素 剩余处理结果 #t)
3. 当前元素非0：
   • 递归处理剩余子列表，得到(处理结果 是否找到最后一个0)
   • 若是否找到最后一个0为#t，说明已过最后一个0，当前元素保留，返回(cons 当前元素 剩余处理结果 #t)
   • 若为#f，说明还没遇到最后一个0，当前元素丢弃，直接返回剩余处理结果和#f

代码实现 #

(define last-non-zero
  (lambda (ls)
    (letrec
        ((lnz
          (lambda (ls)
            (cond
              ((null? ls) (cons '() #f))
              ((zero? (car ls))
               (let ((rest (lnz (cdr ls))))
                 (if (cdr rest)
                     (cons (cons (car ls) (car rest)) #t)
                     (cons (car rest) #t))))
              (else
               (let ((rest (lnz (cdr ls))))
                 (if (cdr rest)
                     (cons (cons (car ls) (car rest)) #t)
                     rest))))))
      (car (lnz ls)))))

等价性验证 #

这个自然递归版本和你用延续性实现的行为完全一致：

• (last-non-zero '(1 2 0 3 4 0 5)) → (5)
• (last-non-zero '(0 1 2 0)) → ()
• (last-non-zero '(1 2 3)) → ()
• (last-non-zero '(0)) → ()
• (last-non-zero '(1 0 2 0 3)) → (3)

内容的提问来源于stack exchange，提问作者Hermann