recursion - 如果在列表中找不到该数字，如何返回 false

Question

所以，我正在尝试解决这个硬件问题:编写一个函数，它接受两个参数，一个列表和一个数字，该函数返回列表中最左边出现的数字的索引。例如:

• 如果 '(1 2 3 3 4) 和 num = 3，则返回 2

• 如果 '(3 2 3 3 4) 和 num = 3，则返回 0

我能够完成那部分，但如果找不到号码怎么办？如果在列表中找不到 num 时我想返回 false 怎么办？我该怎么做？

请记住，我正在尝试以正确的递归而不是尾递归的方式执行此操作。

这是我的代码。

(define (first_elt_occ lst num)
   (cond
       ((null? lst) #f)
       ((eq? (car lst) num) 0)
       (else
          (+ 1 (first_elt_occ (cdr lst) num)))))

(first_elt_occ '(1 2 3 3 4) 3) ;2
(first_elt_occ '(3 2 3 3 4) 3) ;0
(first_elt_occ '(1 2 5 4 3) 3) ;4
(first_elt_occ '(1 2 5 4 3) 6) ;Error 
     ;(makes sense because you can't add boolean expression)

我的另一个问题是，如果我被要求返回列表中最右边出现的数字的索引(正确的递归)，我将如何解决这个问题。例如:'(3 4 5 4 3 7 )，num = 3 返回 4。

谢谢!

Answer 1

正如评论中所建议的，如果我们使用尾递归来实现该过程，这会更容易 - 顺便说一下，尾递归是“正确的递归”，你为什么不这么认为？

通过定义一个名为loop 的辅助过程并将累积的结果传递给参数，我们可以返回#f 或元素的索引:

(define (first_elt_occ lst num)
  (let loop ((lst lst) (acc 0))
    (cond
      ((null? lst) #f)
      ((equal? (car lst) num) acc)
      (else (loop (cdr lst) (add1 acc))))))

如果，对于某些奇怪的要求，您不能在您的解决方案中使用尾递归，则可以重写您的原始解决方案以解决答案为 #f 的情况 - 但这是'既优雅又高效:

(define (first_elt_occ lst num)
  (cond
    ((null? lst) #f)
    ((equal? (car lst) num) 0)
    (else
     (let ((result (first_elt_occ (cdr lst) num)))
       (if (not result) #f (add1 result))))))

无论哪种方式，它都按预期工作:

(first_elt_occ '(1 2 3 3 4) 3) ; 2
(first_elt_occ '(3 2 3 3 4) 3) ; 0
(first_elt_occ '(1 2 5 4 3) 3) ; 4
(first_elt_occ '(1 2 5 4 3) 6) ; #f