0 数列求和

递归解法

(define (recsum li)
    (if (null? (cdr li))
        (car li)
        (+ (car li) (recsum (cdr li)))))

;为了叙述方便，我们这里把数列记为'(1 2 3 4)

所以这个算法的过程大约可以表示如下：

(+ (recsum (1 2 3 4)))
(+ (+ 1 (recsum (2 3 4))))
(+ (+ 1 (+ 2 (recsum (3 4)))))
(+ (+ 1 (+ 2 (+ 3 (recsum (4))))))
(+ (+ 1 (+ 2 (+ 3 (+ 4)))))
(+ (+ 1 (+ 2 (+ 3 4))))
(+ (+ 1 (+ 2 7)))
(+ (+ 1 9))
(+ 10)

看着每行最右侧描成的的折线，我们很容易明白“递归”是什么意思——逐渐“递”到最深的栈，再“归”回最初的一层。而普通递归的弊端也显而易见，有极大的空间复杂度而会爆栈~~（MLE，噔噔咚）醒醒scheme不能oi~~。

因此我们提出了尾递归的概念。

尾递归解法

(define (recsum-tail li)
  (recsum-tail-qwq li 0))
(define (recsum-tail-qwq li i)		;不要注意后缀（
  (if (null? li)
      i
      (recsum-tail-qwq (cdr li) (+ (car li) i))))

同上，表示算法过程为：

(recsum-tail-qwq (1 2 3 4) (+ 0))
(recsum-tail-qwq (2 3 4) (+ 1 0))
(recsum-tail-qwq (3 4) (+ 1 2 0))
(recsum-tail-qwq (4) (+ 1 2 3 0))
(recsum-tail-qwq ('()) (+ 1 2 3 4 0))

也就是说我们实际上是在相当于一遍又一遍地改变着传入recsum-tail-qwq的参数，而这些都是在“第一层”栈里完成的，空间复杂度O(1)~~上一节没写具体空间复杂度是因为我不会算求dalao~~

而从写法来看，即是返回值中递归的函数“在最高层”。

那我们再随便看几个尾递归算法。

1 统计表中元素个数

(define (my-length li)			;length为内置函数
  (my-length-qwq li 0))
(define (my-length-qwq li n)
  (if (null? li)
      n
      (my-length-qwq (cdr li) (+ n 1))))
;在typora上写的，不确定括号数量对（

大同小异。

2 返回删除某元素后的新表

(define (my-remove li n)		;remove为内置函数
  (my-remove-qwq '() li n))
(define (my-remove-qwq l1 l2 n)
    (if (null? l2)
        l1
        (if (equal? (car l2) n)
            (my-remove-qwq l1 (cdr l2) n)
            (my-remove-qwq (cons (car l2) l1) (cdr l2) n))))

注意这个my-remove-qwq返回的是倒序，需要用下一节中的函数倒序处理（需要的话）。

3 表倒序

(define (my-reverse li)
  (my-reverse-qwq '() li))
(define (my-reverse-qwq l1 l2)
  (if (null? l2)
    l1
    (my-reverse-qwq (cons (car l2) l1) (cdr l2))))