Recurrence relation

#1

how can we generate the recurrence relation.

#2

@sunneykumar309 its given in the video itself, do you need clarification with anything?

#3

in Q Friends Problem Recursion we generate recursive formula like f(n)=1*f(n-1)+(n-1)*f(n-2) . But how we will generate it i am not able to think about it by myself.

#4

@sunneykumar309 even that is also explained in the video… i’ll try to explain again.

each person has 2 options, either they can go alone, or they can take someone with them.
if they take a partner, they can choose a partner from N-1 remaining people in (n-1)C1 ways and the remaining answer can be found by f(n-2). Both of these things will happen together, one cant happen without the other, so “AND” case, so we multiply these terms

if they go alone, remaining answer can be found by f(n-1)

Now going alone and going with a partner are 2 different scenarios and cannot happen together, so its a OR case, so we add these terms.

Is it clear now?

1 Like
#5

When I read Prateik Bhaiya, I understand it but I can’t think with myself. what should i do now

#6

@sunneykumar309 dont watch the video directly, first read the question then give some time to think of the solution yourself. Then play the video to see if your approach was correct or not. If its too different from what’s being taught in the video you can try implementing your approach also and see if it is working for different test cases or not, especially the corner cases.

#7

in these q i am not able to figure out when to implement using recurrence relation or solve q by recursive tree?

#8

@sunneykumar309 they are one and the same thing only. The question is when to use memoization. Try to use it whenever possible, but only if there are repeating subproblems and an optimal substructure.
Like for this problem if we take n as some big number, you will see it has repeating subproblems, and since we were able to reduce it to a smaller problem from which we can produce the bigger answer, it has optimal substructure as well.

#9

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.