Блог пользователя ChevishaUchiha

Recursion based problems
Автор ChevishaUchiha, история, 6 лет назад, По-английски

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

  • Проголосовать: нравится
  • +15
  • Проголосовать: не нравится

»
6 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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).

→ Ответить
  • »
    »
    6 лет назад, # ^ |
    ← Rev. 2   Проголосовать: нравится +4 Проголосовать: не нравится

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

    How about backtracking problems?

    → Ответить
    • »
      »
      »
      6 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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.

      → Ответить
    • »
      »
      »
      6 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Na to sam mislio :D

      → Ответить
      • »
        »
        »
        »
        6 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

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

        → Ответить
»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

→ Ответить