Hey guys i am trying to create a function that Takes one parameter:n and then returns the value of the number of moves required to transfer n disks from peg1 to peg 3 in Tower of Hanoi problem. Hints: Total number of moves for n disks, H(n) = 2H(n-1)+1, if n>1 = 1, if n = 1. I have implemented the code in python and it works fine but when i implement it in scheme i come up with a wrong answer. I am very new to scheme and would be thankful if you guys help me to see where i messed up. The code i've come up with is given below:
(define(hanoi n)
(if(< n 2)
1
(+(* 2 (hanoi(- n 1) 1)))))
(display(hanoi 4))
You're passing two parameters to hanoi, but it expects only one, the parentheses are misplaced. This is how the recurrence relation formula looks like in Scheme - and please, take note of how you should indent and format your code! even better, let your editor do it properly for you:
(define (hanoi n)
(if (< n 2)
1
(+ (* 2 (hanoi (- n 1))) 1)))
(hanoi 4)
=> 15
BTW: there's a closed-form solution for this problem, you don't need to write a recursive procedure to find the number of moves - just apply the formula 2**n - 1:
(define (hanoi n)
(- (expt 2 n) 1))
(hanoi 4)
=> 15