can anyone suggest me how to be good at recursion and what should be my approach? From where shall i solve questions?
№ | Пользователь | Рейтинг |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3839 |
3 | Radewoosh | 3646 |
4 | jqdai0815 | 3620 |
4 | Benq | 3620 |
6 | orzdevinwang | 3612 |
7 | Geothermal | 3569 |
7 | cnnfls_csy | 3569 |
9 | ecnerwala | 3494 |
10 | Um_nik | 3396 |
Страны | Города | Организации | Всё → |
№ | Пользователь | Вклад |
---|---|---|
1 | Um_nik | 164 |
2 | maomao90 | 160 |
3 | -is-this-fft- | 159 |
4 | atcoder_official | 158 |
4 | awoo | 158 |
4 | cry | 158 |
7 | adamant | 155 |
8 | nor | 154 |
9 | TheScrasse | 153 |
10 | maroonrk | 152 |
can anyone suggest me how to be good at recursion and what should be my approach? From where shall i solve questions?
Название |
---|
Standard recursion problem are in most cases easy. Recursion becomes harder when you’re solving dp with recursion so try some recursion dp problems.
Solving problems involving dfs is also a good thing to practice recursion.
Try to solve standard problems on dp. If not able to solve, understand it properly and solve some similar problems. Solve 50+ problems(if totally uncomfortable) and you will be good to go.
Check this
Still checking....
Too old joke
Good one mate !!
If you see this reply, don't click on the comment above. (Base case)
You can practice those problems for improving your skill on recursion. I hope it will be helpful for you.
Problems Link: https://codeforces.me/group/MWSDmqGsZm/contest/223339
solve recursion problems, duh
Solve problems tagged DP, Divide and Conquer, DFS and similar, for example 1461D - Divide and Summarize.
Surprisingly only 5 problems are tagged Divide and Conquer but are below 1600 rating.
Recursion? Check this out.
First, you must be good at recursion
ivan100sic can u plz suggest me some good places to start with recursion?
Okay, let's be a bit more serious now.
To be good at recursion, you must first identify simple cases which you will not solve recursively. Depending on the problem, this may be small values of $$$n$$$ e.g. $$$0,1$$$, or leaf nodes of a tree. Then, you must figure out how solving one instance of a problem relates to smaller problems. For example, when finding the maximum depth of a tree, the solution is the maximum of the maximum depths of all direct subtrees, plus one. Finally, when writing the recursive function, put the "simple case check" at the top and return the solution immediately if true, otherwise, make recursive calls, gather all the results, and form the return value based on those.
TLDR, learn from multiple resources. read and watch a lot of examples being solved. and do a lot of examples by yourself, gradually increase level, understand well how recursive code behaves. think of recursion as a method of solving problems by decomposing them into smaller versions. try to write a formal definition of your recursive solutions.
I think a good approach is the following:
Watch and read about recursion in many different resources. This helps me.
Watch or read about as many well-explained examples as you can. You should also try to actively engage and solve at this stage while watching
Now, do as many examples as you can by yourself . If you had some source of feedback, then excellent. if not, it's not a big problem since you should have some ability to self-correct now
Learn, when ready, advanced techniques like DP.
Please note the following:
Always try to well-define relationship between the problem and its subproblems and make it as clear as possible. IDEALLY, express it formally. This will payoff later when you start solving DP problems. example: count the min number of moves needed to solve 3-sticks Hanoi tower with n plates, a good formal expression of the recursive solution is:
Let f(n) denote the answer of n-plates tower. then f(0) = 0
f(n) = f(n-1) + 1 + f(n-1) = 2 * f(n-1) + 1. Now writing code is a piece of cake and also writing iterative solution is very easy. Please note that, the more complex the recursion, the more important is the formal definition.
Solve backtracking problems, especially those with lengthy implementation.