Substitution trace python code

Question

I'm trying to do a substitution trace for this code:

def hanoi(n):
   if n == 1:
       return 1
   else:
       return 2 * hanoi(n - 1) + 1

print hanoi(4)

Output:

This is what I did:

2 * (4 - 1) + 1

2 * (3) + 1

6 + 1

7

I'm not sure what I'm doing wrong.

Kasravnd · Accepted Answer · 2014-09-21 16:41:13Z

3

You have a recursion function and after each step it converted to sub functions with n-1 : Actually you have this :

2 * hanoi(4 - 1) + 1
2 * hanoi(3) + 1
2 * (2 * hanoi(2) + 1) + 1
2 * (2 * (2 * hanoi(1) + 1) + 1)  + 1
2 * (2 * (2 * 1 + 1) + 1) + 1 = 15

answered Sep 21, 2014 at 15:42

Kasravnd

108k19 gold badges167 silver badges195 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

I understand now. I completely forgot to account for the recursion. Thank you for explaining it and showing how its was done.

unutbu · Accepted Answer · 2014-09-21 15:39:51Z

0

2 * hanoi(4-1) + 1 is not the same as 2 * (4-1) + 1

answered Sep 21, 2014 at 15:39

unutbu

886k197 gold badges1.9k silver badges1.7k bronze badges