Recursion Scheme

Question

I have a formula, (2^n)-1, and I need to convert it to a recursion function, I tried several times to rewrite it, but I'm still struggling. What is wrong with my code?

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

(fnum (- n 1)))

Answer 1

You can do it like this (working example):

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

(display (- (pow 5) 1)) 

It is clear that you should split the powering part with the minus 1 step which is going to be performed afterwards.

Answer 2

You need to split the recursion from the substraction:

(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))

Now. The helper can be made local to fnum and even be implemented as named let and then you can add acc parameter to hold the result so that the multiplication doesn't need to be done after each recusion ends. Here is a how I would do it:

;;; 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)))))

It's common to call an iterative tail recursion in named let loop, but I could have kept the name parent-nodes-helper or whatever I found fitting. It's just a name.