尾递归

目录

什么是尾递归

 尾递归是使用递归描述的函数,这种函数的递归一般是在递归的最后返回我们需要的结果,一般的递归是在递归的顶部返回我们需要的结果,所以尾递归需要的内存空间不会随着递归的深度增加而增加。 

阶乘的递归描述

(define (factorial n)
 (if (= n 1)
     1
     (* n (factorial (- n 1)))))

; 这种递归写法我们需要栈空间保存每一次递归,直到递归结束。

阶乘的尾递归描述

(define (factorial n)
  (define (iter product counter)
     (if (> counter n)
        product
       (iter (* counter product) (+ counter 1))
     )
  )
)
; 这种尾递归的写法在递归后我们可以直接抛弃掉调用的堆栈,因为以前的调用对我们要的结果没有一点作用,递归的栈空间保持在常数规模

目录