递归方案

Question

我有一个公式，(2^n)-1，并且我需要将其转换成递归函数。我尝试了几次重写它，但是我仍然很困惑。我的代码有什么问题？

(define fnum(n)
    (if (= n 0) 0
        (- ( * 2 (fnum (- n 1)) 1)))

(fnum (- n 1)))

- Anastasia Cmp

Answer 1

你可以像这样做(工作示例): 最初的回答

(define pow
  (lambda (n)
    (if (= n 0)
      1
      (* 2 (pow (- n 1))))))

(display (- (pow 5) 1)) 

很明显，您应该将接下来要执行的减1步骤与供电部分分开。这样更容易理解。原始答案是"最初的回答"。

- NiVeR

Answer 2

你需要将递归与减法分开处理：

(define (parent-nodes-helper n)
  (if (= n 0) 
      0
      (* 2 (parent-nodes-helper (- n 1)))))

;;; Number of parent nodes in a perfect balanced binary tree
(define (parent-nodes depth)
  (- (parent-nodes-helper depth) 1))

现在，助手可以作为本地变量添加到 fnum 中，甚至可以实现为命名的 let，然后您可以添加 acc 参数来保存结果，这样乘法就不需要在每次递归结束后执行。以下是我会这样做的方法：

;;; Number of parent nodes in a perfect balanced binary tree
(define (parent-nodes depth)
  (let loop ((n depth) (acc 1))
    (if (zero? n) 
        (- acc 1)
        (loop (- n 1) (* acc 2)))))

通常在命名的let中将迭代尾递归称为loop，但我可以保留名称parent-nodes-helper或任何我认为合适的名称。这只是一个名称。

- Sylwester