Register

Recursive function

1,310 views
0 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 1 vote

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

 

 

Voting & Accepting an answer helps improve the community
← Previous · Gate@Zeal 2023 Test ...Next → · Accesing time
← Previous in category · data structure and a...Next in category → · GO Classes Scholarsh...
Position:
Show:

Related questions

1 1 vote
2 2 answers
522
522 views
Vishnu__ asked Feb 4
522 views
Recursive function output
#include <stdio.h>int mystery(int n) { if (n == 0) { return 0; } else if (n % 2 == 0) { return mystery(n / 2); } else { return 1 + mystery(n...
2 2 votes
3 answers 3 answers
1.9k
1.9k views
jverma asked May 23, 2022
1,860 views
Which value of static variable is returned if it is present in return statement of a recursive function?
#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...
4 4 votes
3 answers 3 answers
2.1k
2.1k views
Diksha Aswal asked Jun 27, 2017
2,068 views
Recursive function
int fun(int n) { int s=0,i; if(n<=1) return 1; for(i=1; i*i<n; i++) s+=n; return fun(n/4)+fun(n/4)+s; } what will be the time complexity, returning value and no. of recur...
1 1 vote
1 answers 1 answer
2.5k
2.5k views
radha gogia asked Jul 21, 2015
2,542 views
How many recursive calls are made by gcd function ?
I have already gone through the links of stackoverflow on this topic but still couldn't understand it clearly , so please explain the logic behind this .