Recursive Function Help

[gh24]

Hi guys,

I am having trouble understanding how a recursive function of the following form would work:

float max(float a, float b) {
	return (b < a )? a:b;
} 

float recursive_function(int k, int i, float price){

      if(k=10)

           return max(0,50-price)

      else
           return max((0, 50 - price),
                   (0.53*recursive_function(k+1,i+1,price*1.1)+
                     0.47*recursive_function(k+1,i-1,price/1.1))
}

My confusion isn't really with the recursion and how that works but more so the role that multiplying 0.53 and 0.47 play in the function. How does multiplying the function like that actually affect the outcome of the function?

[Caprico]

Firstly, what is the use of this function? What is it supposed to do? Knowing that would help in the explanation... Else it is slightly complex as it returns a value which has 2 of its arguments as a call to function itself...

[bbgst]

- Line 7 is wrong, it will always return true because you are assigning 10 to k and testing its value. 10 is always true.
- What is the purpose of the variable i? It's not used anywhere inside the function.

[Caprico]

bbgst: if loop doesn't work that way. It'll simply show a compilation error. But thanks fo rpointing out! :)

gh24: Put == instead of =. ...

[Caprico]

And that is what I'm asking.. What is the above funtion supposed to do? What do the variables k, i and price signify?

[gh24]

Yea it should be == , I wrote a simplified version of the actual recursive code I am working with real quickly so that I could get some feedback. The variable i does not really have any purpose at the moment but in some variations of the code it is used. i is also used as a way of checking the code. This is a *simplified* version of a binomial tree that can calculate option prices.

Here is the actual code I am working with:

float american_asian_put_option(int k, int i, float current_stock_price, float current_avg_stock_price) {
	
	if (k == no_of_divisions)

		return max(0.0, strike_price - ((current_avg_stock_price)/(k+1)));

	else 
		return max((strike_price - ((current_avg_stock_price)/(k+1))),

				(uptick_prob*american_asian_put_option(k+1,i+1,current_stock_price*up_factor,((current_avg_stock_price)+(current_stock_price*up_factor)))+ 

				 notick_prob*american_asian_put_option(k+1,i,current_stock_price,(current_avg_stock_price+(current_stock_price))) +

				 downtick_prob*american_asian_put_option(k+1,i-1,current_stock_price/up_factor,(current_avg_stock_price + (current_stock_price/up_factor))))/R);
}

Here strike price, up_factor, uptick_prob, notick_prob and downtick_prob are just numbers that are defined in main.

no_of_divisions is inputted by the user.

current_stock_price is holding the current price of the underlying stock

current_avg_stock_price is supposed to be holding the total value of the underlying stock throughout each path it takes. This is an asian option so the underlying stock price must be averaged over the entire time which is what I am trying to do with the current_avg_stock_price setup.

In main the function is called with (0,0, initial_stock_price, initial_stock_price) and initial stock price is just set in main as a number.

[gh24]

No one has any ideas? I can provide the complete code so you can compile and run it. I also know what the correct output is so I have a way to check if it is correct.

[gh24]

Anyone have any help to offer in regards to the first post even? I've been staring at this code for ages and cannot get it right which means I have some logical issue with it that I just can't seem to grasp...

[gh24]

anyone?!?

Would it help a bunch if I just posted the entire code and the expected output?

I just really need this to work and after a week and half of trial and error I am beginning to get frustrated with it.

[Caprico]

The issue is, you call the function thrice inside the function itself.. So it branches out into three recursions from that point, and then again each into 3, and so on... So its a little complicated to tabulate.. Someone will have to make a table and a flowchart just to keep track of your function... That's probably why no one is replying!

[gh24]

Yea unfortunately I understand the complexity all to well. I was using no_of_divisions equal to 3 and tracking it that way and it appeared as though the values were correct as far as I could tell. What I was unable to understand, however, is where the uptick_prob, notick_prb and downtick_prob play into the function at all. How are they tracked? How do they affect the outcome at all? How can I check if they are affecting the function as I need them to. I believe that my error comes about because I misunderstand how these values affect the outcome which makes my simple arithmetic average produce incorrect values.

[gh24]

Also I have the entire code posted in a different thread if you have any interest in compiling it and seeing what is going on. I also have posted a link to what the function is trying to mimic in the other thread.

[gh24]

So Caprico is there anyway you can look at the first code I wrote (in the original post) and explain to me what the values multiplying the recursive function actually do? For instance I have been testing my actual code (posted in a thread near this one) and I have been changing the multipliers up and I get different final values but I do not see any differences in the outputs of things like the current_stock_price or the current_avg_stock_price.

How can the final values obtained be different if these underlying things which determine the option price do not change? Where is the multiplication actually represented? How can I take into account the multiplication in coming up with a correct average of the path taken to find the average underlying stock price (as I need to do)??

[Peter87]

I'm not sure exactly what you want explained so I just try to explain a few things and hope it helps.

In you initial code, someone calls recursive_function. k, i and price are never changed so they stay the same for the whole function call. when recursive_function is called recursively it calls it with slightly different argument values. Remember that the values of k, i and price is not shared between the different function calls so there will exist different k with different values at the same time (same with i and price).

           return max((0, 50 - price),
                   (0.53*recursive_function(k+1,i+1,price*1.1)+
                     0.47*recursive_function(k+1,i-1,price/1.1))

(0, 50 - price) is probably a typo but it evaluates to 50 - price so I guess it works as you want.
Eventually recursive_function(k+1,i+1,price*1.1) will return a value, lets call it x. recursive_function(k+1,i-1,price/1.1) returns a value as well, we call it y.

return max(50 - price, 0.53*x+0.47*y)
So depending on the values of price, x and y, you will get different values.

k will determine how many recursive calls to do, and price will also affect the outcome but I don't think i will make any difference in output whatsoever because it is never used in any calculation affecting the end result.

Here is an example of how the calls are made just to give you a picture of it works. I have ignored the return values here.

recursive_function(8, 0, 4.0)
	recursive_function(9, 1, 4.4)
		recursive_function(10, 2, 4.84)
		recursive_function(10, 0, 4.0)
	recursive_function(9, 0, 3.63)
		recursive_function(10, 1, 4.0)
		recursive_function(10, -1, 3.30)

[gh24]

You're correct that the (0, 50-price) is wrong. should just be

return max((50 - price),
                   (0.53*recursive_function(k+1,i+1,price*1.1)+
                     0.47*recursive_function(k+1,i-1,price/1.1)

So 50-price is the a part in max and

(0.53*recursive_function(k+1,i+1,price*1.1)+
                     0.47*recursive_function(k+1,i-1,price/1.1))

is the b part of max.

You're right about i not making any difference in price. I am using i currently as more of a check to see what node k is referring to. When together, i and k give a nearly unique view of where on the binomial (or trinomial) tree you are for any given price.

So I understand your output for the recursive function but if I try to take it a step further and get what I need out of the function which is for the function to hold the average price of and I change the function to the following:

float recursive_function(int k, int i, float price, float avg_price){

      if(k==10)

           return max(0,50-avg_price)

      else
           return max((0, 50 - avg_price),
                   (0.53*recursive_function(k+1,i+1,price*1.1, (avg_price +price*1.1)/(k+1))+
                     0.47*recursive_function(k+1,i-1,price/1.1, (avg_price + price/1.1)/(k+1))
}

let's adjust the input to more reasonable numbers of

no_of_divisions = 3;
recursive_function(0,0,60,60)

Intuitively I thought that this would give me an output of:

recursive_function(0, 0,60,60 )
	recursive_function(1, 1, 66,63)
		recursive_function(2, 2, 72.6,66.2)
		recursive_function(2, 0, 60, 62)
	recursive_function(1, -1, 54.54, 57.27)
		recursive_function(2, 0, 60, 58.18)
		recursive_function(2, -2,49.58,54.07)

I do not get those values for the avg_price part when I setup the recursive_function how I have it in this post and that is where I am tripping up in my bigger, more complex code.

I'm sorry, I know I am throwing something completely different at you than I had in the earlier post but I think you just reconfirmed that my understanding of the functionality of the recursive code is correct but my implementation of the avg part is where I am getting tangled.

So as you can see with the avg_price added into the code I also hold onto the overall path information that it takes to get to any given value. This is the part that is really killing me.

The only way I have been able to come close to having the average actually follow through the code is by doing a sum of the entire path and then dividing by (k+1) at the end but I believe this compromises the recursive functions integrity and is the reason for my mistakes. The way I have been trying to get the avg is as follows:

float recursive_function(int k, int i, float price,float total_price){

      if(k==10)

           return max(0,50-total_price/(k+1))

      else
           return max((0, 50 - total_price/(k+1)),
                   (0.53*recursive_function(k+1,i+1,price*1.1, total_price+price*1.1)+
                     0.47*recursive_function(k+1,i-1,total_price + price/1.1))
}

When I do it like that I get the correct avg_prices for the
return max(0,50-total_price/(k+1))

and

return max((0, 50 - total_price/(k+1))

BUT

(0.53*recursive_function(k+1,i+1,price*1.1, total_price+price*1.1)+
                     0.47*recursive_function(k+1,i-1,total_price + price/1.1))

because I feel like taking the avg outside of this function is ignoring the 0.53 and 0.47 multiplication. This analysis also makes sense when considering how close I am to getting the correct values in my other code. I am only a few decimal places off which suggests to me that it is this multiplication that is not being taken into account as it should be. (in the other code I have the multiplied numbers are like 0.501033 and 0.49...).

I do not believe that I am getting the correct values for the




Also a quick note****

your output has a small error, it should actually come out as:

recursive_function(8, 0, 4.0)
	recursive_function(9, 1, 4.4)
		recursive_function(10, 2, 4.84)
		recursive_function(10, 0, 4.0)
	recursive_function(9, -1, 3.63)
		recursive_function(10, 0, 4.0)
		recursive_function(10, -2, 3.30)

Thank you for your help!! I really appreciate it!

[gh24]

@peter87 any thoughts? Have you had a chance to take a look at my response?

Edit: I believe passing the avg_price by reference may be in order but I still am not sure about implementation...

[bbgst]

Caprico wrote:

bbgst: if loop doesn't work that way. It'll simply show a compilation error. But thanks fo rpointing out! :)

Actually, it does. When you write

if(x = 1)

the variable x gets assigned 1 and it's value is tested. Since its 1 and 1 is true, the code inside if is executed. If, instead, you wrote:

if(x = 0)

the else code would be executed, since the value assigned to x is 0, thus, false.

[gh24]

I still can't get the current_avg_stock_price to be in the function, any help would be great.

[gh24]

So can anyone explain the initial question in this post? How does multiplying 0.53 and 0.47 by the recursive function actually affect the outcome and where does that materialize if I were to try and check to make sure it was multiplying and affecting the overall value or the recursion?

function was:

float recursive_function(int k, int i, float price, float avg_price){

      if(k==10)

           return max(0,50-avg_price)

      else
           return max((0, 50 - avg_price),
                   (0.53*recursive_function(k+1,i+1,price*1.1, (avg_price +price*1.1)/(k+1))+
                     0.47*recursive_function(k+1,i-1,price/1.1, (avg_price + price/1.1)/(k+1))
}

[Caprico]

.53 and .47 probably act as determinate multiplying constants, and yes, they will affect the outcome... Take the case of k=8, as a start: (Also assume that the max is always the recursive value). Also, for simplicity, I am writing avg_price as a, and price as p and these represent initial values throughout, for simplicity:

k=8, so it returns:

0.53*recursive_function(9, i+1, p*1.1, (a+p*1.1)/9) + .47*recursive_function (9, i-1, p/1.1, (a +p/1.1)/9)

Let us write this as .53*(1) + .47*(2):

1 is:

.53*recursive_function(10, i+2, p*1.21, ((a+p*1.1)/9+1.21*p)/10) + .47*recursive_function (10, i, p, ((a+1.1*p)/9+p)/10)

2 comes similarly..

This will now return max between 0 and 50-avg_price since k is now 10...

Do you see how .53 and .47 work now? They successively keep on multiplying, and will eventually lead upto a certain change in the final returned value... If you want to see how it affects the final answer, simply remove the constants... Though there won't be a discernible pattern in the values obtained with and without the constants (since your algorithm for the function is highly complicated, atleast for me, (a student)), but there will definitely be a change...