okay so i saw the video and understood the solution but what the video fails to provide is how one must approach this question , because after explaining the question the video jumps right into writing the solution, yes it explains each line and how it is working but the main fact is it does not tell how do i think of that solution? how to come up with that solution? this video basically feels like a udemy video where the instructor writes a piece of code and then tells you okay this code does this , this code does that .
How to approach this?
@shikhar07,
Any recursive function needs to have two parts:
- A base case, in which the function can return the result immediately
- A recursive case, in which the function must call itself to break the current problem down to a simpler level
Go through the following thought process in order to decide how the recursive call should be structured:
- Break the problem you are trying to solve down into a problem that is one step simpler
- Assume that your function will work to solve the simpler problem — really believe it beyond any doubt
- Ask yourself: Since you know you can solve the simpler problem, how would you solve the more complex problem?
First get the base case done. After that just think of a shorter problem and write code for that.
Example:
QuickSort to sort an array of numbers:
- If there are only two elements, put the bigger after the smaller one, you’re done.
- Otherwise, choose an element e at random; go over the array and put all elements bigger than e after it, and all those smaller than e before it.
- Use Quicksort to sort the lower part; Use Quicksort to sort the upper part (Quicksort’s greatest merit is that these two sorts can be done in parallel)
That’s it. No need to go into details, each one of these sub-sorts and sub-sub sorts will eventually get to stage (1) where the actual work is done.
Recursion is sometimes about that leap of faith you need to take that your function will work and return the correct answer for a smaller problem
okay i followed these steps and did the same,I followed the processes in the previous videos and Step 1:- if(arr[si]==data)
{
return new int[si];
}
i checked with the curr element if so then returned a new array containing the index,then my step 2:- int output[]=allIndices(arr,si+1,data);
because i assumed that recursion will get me the answer,then Step-3 was base case which i did …i dint get the answer so i want to know where and how my assumptions were wrong ? and here is the code:-
public static int[] allIndices(int arr[],int si,int data)
{
if(si==arr.length)
{
int a[]= {};
return a;
}
if(arr[si]==data)
{
return new int[si];
}
int output[]=allIndices(arr,si+1,data);
return output;
}@shikhar07,
Okay. Let’s see line by line what is happening in your code.
Say the input array is 1 2 5 5 2 and data = 5, Start index = 0. Ideally the output should be 2 3.
We enter the array and first condition is si==arr.length which is false. Then the next block is arr[si] == data which is again false since 1 != 5.
Next is int output[ ] = allIndices(arr, 1, data); Now we enter a recursive call where start index is 1. Again this will be false for both the if cases. Hence we go on to the next recursive call with si = 2.
Next recursive call is int output [ ] = allIndices(arr, 2, data);
Now we enter the function where start index = 2;
For this the first if condition is false. The second is true. since arr[2] ==5 and data == 5. Hence we return a new int array of the size si. So we are just returning a blank array of size 2.
Now we go on to the previous function in the method stack where si = 1 (from which the call for si=2 was made)
allIndices(arr,2,data) returned a blank array of size 2.
(in the function where si =1) int output [ ] = new int[ 2 ]. Next line is return output. Hence we go back to the function from which this call was made, and that is allIndices(arr,0,data).
And again we just return the output array back to our main function as answer.
@shikhar07,
The error is well, you are not updating the array at any point. We are just returning an array of the size of the first index where the element was first found.
Even if the input array is: 1 2 5 2 and data = 5
You will get the same answer as 1 2 5 5 2 with data= 5.
okay i have understood that i am not updating the array at any point , so assuming that recursion will do the work and taking leap of faith , step 1- would be to check if(arr[si]==data) after that what should i do? how should i update because i understood that if i do if(arr[si]==data)
{
int op[]={si};
return op;
} then suppose i found at index 2 then from there it self it will return , and the data could be found at index 3 or index 4 and so on…so what i think is i should go till the end and traverse back , like if i found at index 4 then include that in the array then again check at index 3 if found then again include that in array and so on till index 0.
@shikhar07,
You need to keep a count variable to keep a check on number of occurrences of the value. And when si==arr.length() we will return a array of size count. Also, we will do some work when we return to our previous function and that will be to store the index.
Yes this is what is explained in the video , ok so what my mistake was i just assumed that my recursion will work but only that wont be enough , i have to do the dry run reach till the base case and understand there that ok now that i have reached the base case what can i do from here, and here we have to create an array of size count and then keep adding the index. Now i understand that why i kept questioning that how do i know what i have assumed for recursion is correct , and ans to that would be to do the dry run and then make the required changes…am i right ?
@shikhar07,
Yes I think you are correct. Recursion is all about the leap of faith in your own code. Base case and what work the recursion is doing. these are important.
this was a simpler problem , so easy to follow the recursion and reach base case then think of how to proceed from there but for tougher problems its not possible to draw recursion tree , what to do that time?
@shikhar07,
Okay so for a larger problem you can only think about the problem which is base case + 1, that is the problem from which the base case will be called
I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.
On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.
Yes , my doubt was cleared Thanks 