Mystery(p, q)
1. If p == 0
R = ⌊p / 2⌋
2. return 0
3.
4. S=q+q
5. t = Mystery(R, S)
6. If p is even
7. return t
8. else
9. return t + q
Initial Input:
Mystery(100, 150)
Here p=10, q=150.
Step-by-Step Execution:
1. First Call: Mystery(100, 150)
o p=100 (even, not 0).
o R=⌊100/2⌋=50.
o S=150+150=300.
o Recursive call: t=Mystery(50,300).
2. Second Call: Mystery(50, 300)
o p=50 (even, not 0).
o R=⌊50/2⌋=25.
o S=300+300=600.
o Recursive call: t=Mystery(25,600).
3. Third Call: Mystery(25, 600)
o p=25 (odd, not 0).
o R=⌊25/2⌋=12.
o S=600+600=1200.
o Recursive call: t=Mystery(12,1200).
4. Fourth Call: Mystery(12, 1200)
o p=12 (even, not 0).
o R=⌊12/2⌋=6.
o S=1200+1200=2400.
o Recursive call: t=Mystery(6,2400).
5. Fifth Call: Mystery(6, 2400)
o p=6 (even, not 0).
o R=⌊6/2⌋=3.
o S=2400+2400=4800.
o Recursive call: t=Mystery(3,4800).
6. Sixth Call: Mystery(3, 4800)
o p=3 (odd, not 0).
o R=⌊3/2⌋=1.
o S=4800+4800=9600.
o Recursive call: t=Mystery(1,9600).
7. Seventh Call: Mystery(1, 9600)
o p=1 (odd, not 0).
o R=⌊1/2⌋=0.
o S=9600+9600=19200.
o Recursive call: t=Mystery(0,19200).
8. Base Case: Mystery(0, 19200)
o p=0 Return 0.
Backtracking Results:
1. Seventh Call: Mystery(1, 9600)
o t=0.
o p=1 (odd), so return t+q=0+9600=9600.
2. Sixth Call: Mystery(3, 4800)
o t=9600.
o p=3 (odd), so return t+q=9600+4800=14400.
3. Fifth Call: Mystery(6, 2400)
o t=14400.
o p=6 (even), so return t=14400.
4. Fourth Call: Mystery(12, 1200)
o t=14400.
o p=12 (even), so return t=14400.
5. Third Call: Mystery(25, 600)
o t=14400.
o p=25 (odd), so return t+q=14400+600=15000.
6. Second Call: Mystery(50, 300)
o t=15000.
o p=50 (even), so return t=15000.
7. First Call: Mystery(100, 150)
o t=15000.
o p=100 (even), so return t=15000.
Final Result:
Mystery(100, 150) returns 15000
