Recursive Binomial Tree Code, can't do more than 5 steps... why?

Question

function [y]=AmericanPutClassic (St,t)
% S0 = 100;
K = 100;
r = 0.05;
sigma = 0.3;
T = 2;
nsteps = 5;
% St
dt = T / nsteps;
u=exp(sigma*sqrt(dt));
d=1/u;

Pu=(exp(r*dt)-d)/(u-d);
Pd=1-Pu;

if t==T
    y=max(K-St,0);
    return
elseif t<T
    upPrice=AmericanPutClassic(St*u,t+dt);
    downPrice=AmericanPutClassic(St*d,t+dt);
    PrevPrice=(Pu*upPrice+Pd*downPrice)*exp(-r*dt);
    if max(K-St,0) > PrevPrice
        y=max(K-St,0);
    else 
        y=PrevPrice;
    end
    return
end
end

I think my code does the job, but when I make 'nsteps' higher than 5, it crushes... I keep getting different errors... now it just says there is problem with my code when its higher than 5... before it would say: "??? Maximum recursion limit of 500 reached. Use set(0,'RecursionLimit',N) to change the limit. Be aware that exceeding your available stack space can crash MATLAB and/or your computer."

can anybody spot the problem? I start by calling AmericanPutClassic(100,0)...

Thanks

Answer 1

I don't know what you're trying to do but this problem has been described so many time on SO it's not funny anymore.

Let's paint a picture:

you start off with

dt = T / nsteps;

which is my first red flag.

then you do:

if t==T

where t = t + dt

Why is that wrong? Because of this wonderful thing called quantization. In other words there will be a time when because of super small micro difference, the result will not be correct. The bigger nsteps is, the worse this will be.

And then to add insult to injury, you put this line in

elseif t<T ... end

which means your code will skip everything, and you'll return nothing, causing your code to crash.

How does one solve this? If you can move integers around instead of floating values, you'll be in a better position. So instead of dt, you can have currentStep, such that:

function [y]=AmericanPutClassic (St, currentStep)
if nargin < 2
    currentStep = 0;
end
...
if currentStep>=nsteps % if t==T
...
else
...
    upPrice=AmericanPutClassic(St*u,currentStep+1);
...
end