球拍:确定尾巴递归吗? [英] Racket: Identifying tail recursion?

问题描述

我在球拍中编写了两个不同的函数，以确定数字列表是否在递增:

I wrote two different functions in racket to determine whether a list of numbers is ascending:

(define (ascending list)
  (if (<= (length list) 1)
      #t
      (and (< (car list) (car (cdr list))) (ascending (cdr list)))))

(define (ascending-tail list)
  (ascending-tail-helper #t list))

(define (ascending-tail-helper prevBool rest)
  (if (<= (length rest) 1)
      prevBool
      (ascending-tail-helper (and prevBool (< (car rest) (car (cdr rest)))) (cdr rest))))

我很难确定第一个升序是否是尾递归，所以我使用了我认为是尾递归的方法重写了它.

I had the hardest time determining whether or not the first ascending was tail recursive, so I rewrote it using what I believe to be tail recursion.

我之所以回顾性地认为第一个不是尾递归，是因为我相信在递归的每个级别上，该函数都将等待和"语句中的第二个参数返回，然后才能评估布尔值表达.相反，对于递尾帮助程序，在执行递归调用之前，我可以评估小于表达式的值.

The reason why I retrospectively believe the first one to not be tail recursive is that I believe at each level of recursion, the function will be waiting for the second argument in the "and" statement to return before it can evaluate the boolean expression. Conversely, for ascending-tail-helper, I am able to evaluate the lesser than expression before I do my recursive call.

这是正确的吗?还是让我比以前更加困惑?

Is this correct, or did I make myself even more confused than before?

推荐答案

您是正确的，在第一个版本中，递归调用返回到and，而在第二个版本中，递归调用是尾调用.

You are correct, in the first version the recursive call returns to and, whereas in the second version the recursive call is a tail call.

但是，and是宏，通常使用if

However, and is a macro, and is generally expanded using if

(define (ascending list)
  (if (<= (length list) 1)
      #t
      (if (< (car list) (car (cdr list)))
          (ascending (cdr list))
           #f)))

这是尾递归的.

这篇关于球拍:确定尾巴递归吗?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！