递归计划

Question

我有一个公式，（2 ^ n）-1，我需要将它转换为递归函数，我尝试了几次来重写它，但我仍在苦苦挣扎。我的代码出了什么问题？

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

(fnum (- n 1)))

Answer 1

你可以这样做（working example）：

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

(display (- (pow 5) 1)) 

很明显，您应该将动力部分与减1步骤分开，之后将执行。

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或我发现的任何拟合。这只是一个名字。