i_m_jp99's blog

By i_m_jp99, history, 3 years ago, In English

can anyone suggest me how to be good at recursion and what should be my approach? From where shall i solve questions?

  • Vote: I like it
  • 0
  • Vote: I do not like it

| Write comment?
»
3 years ago, # |
  Vote: I like it +9 Vote: I do not like it

Standard recursion problem are in most cases easy. Recursion becomes harder when you’re solving dp with recursion so try some recursion dp problems.

»
3 years ago, # |
  Vote: I like it +25 Vote: I do not like it

Solving problems involving dfs is also a good thing to practice recursion.

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

»
3 years ago, # |
  Vote: I like it +160 Vote: I do not like it

Check this

»
3 years ago, # |
Rev. 2   Vote: I like it +4 Vote: I do not like it

You can practice those problems for improving your skill on recursion. I hope it will be helpful for you.

Problems Link: https://codeforces.com/group/MWSDmqGsZm/contest/223339

»
3 years ago, # |
  Vote: I like it +12 Vote: I do not like it

solve recursion problems, duh

»
3 years ago, # |
Rev. 2   Vote: I like it +4 Vote: I do not like it

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.

»
3 years ago, # |
  Vote: I like it -6 Vote: I do not like it

Recursion? Check this out.

»
3 years ago, # |
  Vote: I like it +77 Vote: I do not like it

First, you must be good at recursion

  • »
    »
    3 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    ivan100sic can u plz suggest me some good places to start with recursion?

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +20 Vote: I do not like it

      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.

»
3 years ago, # |
Rev. 3   Vote: I like it +1 Vote: I do not like it

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.

Some details
»
3 years ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

Solve backtracking problems, especially those with lengthy implementation.