senshi2504's blog

By senshi2504, history, 4 years ago, In English

http://codeforces.com/contest/767/problem/C

I have done some very basic questions of DFS , but I always feel confused and not so sure about , how to systematically formulate my solution in the dfs code . I feel confused , wheather to place certain statements before or after the recurssive call. A similar situation happens for this problem too . I came up with the idea , but feel lost when I have to code it in the dfs solution. I would request this community , to please share your approaches towards handling such DFS codes . Thanks :)

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

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

Whenever you have to write recursive codes, never think about how the recursions will go in the middle. Just think at one step what decisions you can make and make those recursive calls. And finally set the base cases. If you think about the recursions trees, then your head will blow.

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

    Thankyou for the advice , I shall try to follow it :)

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

DFS is usually done recursively. This algorithm can be easily learnt from a lot of online sources. So I think that learning DFS is not the issue here. I think that you are not so familiar with recursion, which is hindering you from implementing DFS.

This is my paradigm for formulating recursive solutions (the same applies for DFS):

For any recursion, there must be similar subproblems (note that similarity of subproblems is very important, if they are not the same, your recursion will break).

Now we try to formulate our recursion:

  1. How do we transition from the current problem to a smaller subproblem? (Inductive step)
  2. What are our base cases?

Let's see an example of this:

Let's say that we want to sum the numbers in the list [1,2,3,4,5,6,7].

What are our subproblems? We need to sum the numbers from some position i to the end of the list (e.g. [3,4,5,6,7]).

Now we are ready to formulate a recursive solution:

Let our recursive function be sum( list of numbers ) which gets the sum of numbers from the given list.

Inductive step

Let's say we are currently working on the subproblem [ 2,3,4,5,6,7 ]. Now we just need to keep the first number in that subproblem (i.e. 2) and call our recursive function for [ 3,4,5,6,7 ]. We don't care what happens next — we assume that (by magic), we will automatically be able to compute the result for the rest of the list. Now we add this result to the number which we took at first, which is 2. Hence, the answer for this sub-problem will be 2 + sum( [3,4,5,6,7] ) which will be 2 + 25 = 27. We will now return this result to the function that called sum( [2,3,4,5,6,7] ). Hence, the call to sum( [1,2,3,4,5,6,7] ) gives us the sum of all the numbers in the list.

Base Case

This is very important and must not be overlooked. Base case essentially means, when will your algorithm stop? In this case, we want to stop when the list of numbers is empty (i.e. we call sum( [ ] ). This might seem trivial at first, but you must ensure that your recursion will definitely reach one of the base cases.

Let's say we want to sum every 2 numbers starting from the beginning of the list instead. A BIG mistake would be to check that we have reached exactly 1 position after the last element in the list). Note that we are jumping in steps of 2. So, our recursion may reach 2 positions after the last element in the list. So you have to ensure that your algorithm covers all possible terminal conditions.

One problem which I would recommend you to try to test your understanding of recursion is to code the recursive solution to generate fibonacci numbers. Try to use the above-mentioned format to devise your solution without looking at model answers.

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

    I appreciate the answer , but I have certainly done a few recursive problems , in the past , including the two that you mentioned. But my problem is that , it takes me a lot of time to come up with the DFS code to solve the problem. And it is because , I always draw the call stack to check my calls and variables , and that is quite cumbersome. However , I have seen many coders ,can do so in one attempt , and that to quickly . So I am just trying to reach that stage . Again thanks for your advice