Consider the function int bbox (int size, int []a,int x) { If (size==1)return 1;
ID: 3903146 • Letter: C
Question
Consider the function int bbox (int size, int []a,int x) { If (size==1)return 1; Int y=0; If(a[size-1]>x) y=1; Return (y+bbox(size-1,a,a[size-1]);
Find bbox(8,a,10) where the array a is [9,3,2,5,6,1,8,4]
Consider the function int bbox (int size, int []a,int x) { If (size==1)return 1; Int y=0; If(a[size-1]>x) y=1; Return (y+bbox(size-1,a,a[size-1]);
Find bbox(8,a,10) where the array a is [9,3,2,5,6,1,8,4] { If (size==1)return 1; Int y=0; If(a[size-1]>x) y=1; Return (y+bbox(size-1,a,a[size-1]);
Find bbox(8,a,10) where the array a is [9,3,2,5,6,1,8,4]
Explanation / Answer
As this question involves the concept of Recursive Fuctions.So, we first understand how recurssive fuctions solves a particular problem.
A fuction is said to be recursive if it calls itself again and again untill a certain condition meets.
In our question, the fuction bbox(int size,int a[],int x) is a recursive function. As it calls itself in 5th line of programmme as Return (y+bbox(size-1,a,a[size-1]) .
Now we learn how to solve a problem involving recursive functions.
Recursive function uses STACK paradigm to solve a problem
For example, A recursive FACTORIAL fuction is like,
factorial(int n)
{ if(n==1) return 1;
else return(n*factorial(n-1)):
}
So, if want to find factolial of 5 i.e factorial (5), then it will be solved internally as follows,
factorial (5) = 5 * factorial (4)
factorial (4) = 4 * factorial (3)
factorial (3) = 3 * factorial (2)
factorial (2) = 2 * factorial (1)
factorial (1) =1
now, if we put value for facorial (1) =1 to calculate value for factorial(2) and so on in upward direction.
LIKEWISE, our above question can be solved like this and the pattern of solution for the recursive funvtion is like,
bbox(8,a,10) = 0 + bbox(7,a,4) because here y=0 as a[7]=4 is less than 10
bbox(7,a,4) = 1 + bbox(6,a,8) because here y=1 as a[6]=8 is greater than 4
bbox(6,a,8) = 0 + bbox(5,a,1) because here y=0 as a[5]=1 is less than 8
bbox(5,a,1) = 1 + bbox(4,a,6) because here y=1 as a[4]=6 is greater than 1
bbox(4,a,6) = 0 + bbox(3,a,5) because here y=1 as a[3]=5 is less than 6
bbox(3,a,5) = 0 + bbox(2,a,2) because here y=1 as a[2]=2 is less than 5
bbox(2,a,2) = 1 + bbox(1,a,3) because here y=1 as a[1]=3 is greater than 2
bbox(1,a,3) = 1 as here size=1 therefore it return 1.
Hence, the answer will be 0+1+0+1+0+0+1+1 = 4
Therefore, bbox(8,a,10) = 4