Noneqw's blog

recursion trouble :(
By Noneqw, history, 4 years ago, In English

Hello codeforces,

i have take many recursion tutorials , but i still couldn't solve a lot of recursive style problems and if i see their solutions i can't trace it executing , so also i can't learn DP well :(

please give me advises to solve this trouble and best tutorials and best platforms to training on recursion problems

thanks in advance...

  • Vote: I like it
  • +6
  • Vote: I do not like it

Comments Comments (12)
| Write comment?
»
4 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Maybe some more exercise could help =)))) you could search in a2oj categories for some DP and if you're in trouble just looking for some solution on Quora =)))) many solutions is DP with memozation and that not mean you cant learn DP well

→ Reply
»
4 years ago, # |
  Vote: I like it +7 Vote: I do not like it

recursion trouble

→ Reply
»
4 years ago, # |
  Vote: I like it +1 Vote: I do not like it

There's no complate or style for recursion.I think dp is easier to understand than recursion.dp is more intuitive

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    How can he make transitions if he cannot understand recursions? Thinking about states of a DP is easy compared to making a transition. Usually, transitions are easy. But a few times they are hard.

    → Reply
»
4 years ago, # |
  Vote: I like it +1 Vote: I do not like it

These two helped me a lot during my initial days. You can give it a try. I hope you will get some help.

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I understand. Recursion is difficult to think. Here's how I would approach them: 1. Understand the problem and jot down all the properties you notice. 2. See how you can get the answer for the current state by knowing the answers of subproblems. 3. Think of the answer for the basic state like n = 0 or something.

Let me help you. Please go through 1369D - TediousLee and think for a solution (not telling you Fibonacci as you would have gone through it a thousand times).

What I notice here is the fact that RDB(n) is made of 2 RDB(n — 2) trees and one RDB(n — 1) tree (see and draw more examples to understand).

So, answer is RDB(n) = 2 * RDB(n — 2) + RDB(n — 1) + (i % 3 == 0). Eg: n = 6 So it consists of RDB(4) and RDB(5). Notice that in both RDB(4) and RDB(5), nodes 4 and 5 are not part of the claws respectively. Therefore, (6 4 5 4) claw is added. That explains the equation.

Point being the main recursion formula is derived by some properties in the problem. With time and practice, it will become clearer. DP is memoizing the values you calculate in recursion, so we need not calculate them again.

Not a great explanation but I hope you get the point.

→ Reply
»
4 years ago, # |
  Vote: I like it +2 Vote: I do not like it

I like to think of recursion as a Tree it really does help me with visualization

→ Reply