629 views
0 votes
0 votes
Consider the following recursive function which is used by dynamic programming.

T(n) = { 0; if n<1

                1; if n=1

                T(n-1)+T(n-2)+1; if n>1}

Assume for every function call T(i) it checks the table first , if it's 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) computed for first time its return value is stored in the table to avoid redundant function calls. If system allocated 48 bytes for stack allocation , then the maximum value of 'n' so that overflow cannot occur . ( Assume system allocate 4 byte to each stack entry which is sufficient for storing required data.)

1 Answer

1 votes
1 votes

The function calling is done in preorder while return value in given in post order meaning whenever we call T(n) then T(n-1) we be called first and T(n-2) will only be called once T(n-1) has returned value.

So we begin with n=12 then n=11 is called but n=10 waits until n=11 returns value,

Similarly n=11 calls n=10 but n=9 waits till n =10 returns value.

This goes one till n=1 where we get 1 as return value, so from 12 to 1 we have 12 function calls whose entry will reside in stack at same time and 12x4 =48 will be entry size.

the key point to keep in mind is the order of function calls which is preorder.

Here’s a similar question : GATE CSE 1994 | Question: 21 - GATE Overflow for GATE CSE

 

 

Related questions

1 votes
1 votes
3 answers
1
jverma asked May 23, 2022
1,030 views
#include <stdio.h>int f(int n){ static int r = 0; if (n <= 0) return 1; r=n; return f(n-1) + r;}int main() { printf("output is %d", f(5)); return 0;}Ou...
0 votes
0 votes
0 answers
2
hacker16 asked Apr 28, 2018
466 views
What is the max height of recursion tree of recurrence $c(100,50)$?here, the recursive function is defined as$c(n,k) = c(n-1,k-1) + c(n,k-1)$terminating condition$c(n,n) ...