Схема рекурсии

Question

У меня есть формула, (2 ^ n) -1, и мне нужно преобразовать ее в функцию рекурсии, я несколько раз пытался переписать ее, но я все еще борюсь.Что не так с моим кодом?

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

(fnum (- n 1)))

Answer 1

Вам нужно отделить рекурсию от вычитания:

(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 или любое другое, что мне показалось подходящим.Это просто имя.

Answer 2

Вы можете сделать это так ( рабочий пример ):

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

(display (- (pow 5) 1)) 

Понятно, что вы должны разделить питающую часть с шагом минус 1, который будет выполненпосле этого.