Recursion

Question

Consider the following recursive function which is used by dynamic programming.

Assume for every function call T(i) it checks the table first, if its value is already computed it retrieves the value from table. Otherwise it calls a recursive function call to compute its return value. Whenever a function T(i) computes for first time its return value is stored in the table to avoid the redundant function calls.
The number of function calls that need the support of stack to complete the execution of the function T(12) are __________ .

Comments

post again ! photo not loading !

---

Edited post.

---

is it 21 ?

---

Is 5 the answer?

Answer 1

It should be $\large\color{red}{21}$

Comments

@Debashish,

This code allows storing the values in the table. Every call is not a fresh call.

---

ok ! I got your point ..mark the redundancy in the above diagram.

---

Yes, Redundant calls need to be excluded .

---

I am asking if there is any redundancy please point out...I think mine is ok! ..that may be wrong!

---

I too think no redundancy in above tree.

---

In the above diagram, Do both the 7's need the support of the stack. If one is calculated and saved in the table, then other can be used.

Do both the 5's and both the 3's need stack support ? Is there any need to make a stack frame of the duplicates ?

---

@kapil your QS might be...why call $7$ again from f(9) ??

My answer is: to check $7$ in the table f(7) must be invoked first and pushed on to the stack. After that check for $7$ and found. SO no further call from f(7) function frame.

If this is not the reason.. then please mention.

---

srry I was writing a comment and posted !

---

then you are asking check for $7$ in the f(9) frame ???

---

T(9) = T(7) + T(6) 

 T(7)  checks the table first, if its value is already computed it retrieves the value from table. Otherwise it calls a recursive function call.

When T(7) is already computed from T(10), then getting T(7) again, which has to be checked first and then called(This is function call), right ?

---

cache[N+1]; // memoization table//

type function(int n) {
	if(cache[n]!= -1) {
		return cache[n];
	}else {
		cache[n] = function(n-2) + function(n-3);
	}
	return cache[n];
}

int main() {
	
	/* code */

	for(int i=0;i<=N;i++) {
		cache[i] = -1; // initialize with something that
									// will not be used
	}

	// base cases 
	// neglect -ve index for time being

	cache[0] = base_value1;
	cache[1] = base_value2;
	
	// call now
	function(n);

	/* code */

}

---

When T(7) is already computed from T(10), then getting T(7) again

• T(7) is already computed from T(10). how to know that ?
• we will know that after getting inside a new f(7) frame again and check for n = 7 in the table or not ?
•  

  then getting T(7) again

• When we know f(7) is coming again ? in f(9) ? NO 
• in f(9) we will check for $n = 9$ only. $9$ is not in the table. so we will expand $7$ and $6$

---

Simply tell me one thing.

What is the answer if the question says unique function calls ?

---

possible distinct values of n

---

A similar example of a look-up table in CLRS in matrix chain multiplication:

---

@Debashish

"T(7) is already computed from T(10). how to know that ?"

it can known during execution.

"The number of function calls that need the support of stack to complete the execution of the function"

This is a bit ambiguous- but in all probability should be referring to number of function where a function call is made during runtime.

---

Yes sir ..

But, I followed what QS says - 

Assume for every function call T(i) it checks the table first, if its value is already computed it retrieves the value from table. Otherwise it calls a recursive function call to compute its return value.

In a call to f(9):

1. table[9] is searched
2. if valid data found in table[9] , return table[9]
3. if NO valid data found in table[9]
4. Then, call recursive function f(7) and f(6)

Sir, If we need to avoid calling again f(7)  inside f(9),something needs to added in between step$3$ and step$4$.  

I think the steps will be like this.

In a call to f(9):

1. flag1 = 0,flag2 = 0;
2. table[9] is searched
3. if valid data found in table[9] , return table[9]
4. if NO valid data found in table[9],Then
5. check table[7] : if no valid data found set flag1 
6. check table[6] : if no valid data found set flag2
7. if(flag1) call f(7)
8. if(falg2) call f(6)

 Or, any other way to avoid calling f(7) in runtime ?

---

@Arjun Sir,

So shouldn't this be only distinct function calls that we make ?

---

@Debashish you are correct. @Kapil, see the last comment by Debashish

---

@Arjun sir

then sir what is the answer 10 or 11.