ChevishaUchiha's blog

Recursion based problems
By ChevishaUchiha, history, 5 years ago, In English

Hi, can you give me some set of recursion-based problems (brute-force or anything similar) ?

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

Comments Comments (6)
| Write comment?
»
5 years ago, # |
  Vote: I like it +3 Vote: I do not like it

I don't think there's anything like 'recursion based problems'. Recursion isn't very advisable method of solving the problems because its implementation is inefficient. As each function call uses some memory, it may eventually lead to the stack overflow problem. Of course, recursion may be a very good way to simplify the algorithm what surely helps you to understand how it works (and why it's correct). It also makes an implementation easier what's valuable during the contest. But anyway, there always exists some (better) solution which doesn't use recursion. A good example is DP. You can write top-down DP which is usually more obvious and shorter but there's always some bottom-up DP which is more efficient. Though if you think you need some training in recursion, you can take any DP problem as it has two ways of solving: bottom-up and top-down (with recursion).

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

    I don't think there's anything like 'recursion based problems'.

    How about backtracking problems?

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

      Good example. Backtracking problems are these in which recursion is usually used. Although it's the best way of solving during the contest (because of time), it doesn't mean other ones don't exist. Each call of recursive function have some initial set of values which outline the state in which we are. We can always pack this set of values into one object and make a stack of this objects. It's how we can avoid using recursion. Usually it's even simpler as we can do it by several nested loops. I think we can distinguish two types of recursion. 1)programming recursion — when we really call a function in itself. It can be always avoided. 2)algorithmic recursion — when we have recursive algorithm, then this recursion exists in our way of thinking, regardless its later implementation. We can often find recursion algorithms in DP and (as you've mentioned) backtracking.

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

      Na to sam mislio :D

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

        In that case, you can read about it in CP3 and try solving UVa problems.

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

Search for problems with the tag "divide and conquer" its the modern term for recursion. https://codeforces.com/problemset?tags=divide+and+conquer

→ Reply