We see many problems now and them.it’s even hard to visualize and find the answer.
I think these problems can be solved easily using recursive techniques but I am actually confused how to avoid the cycles in recursion.
Can anyone suggest me good tutorials for recursion.
Thank you…
you can avoid recursion by using iteration because recursion takes more time hence you can replace it by iteration by storing data at each level and using them for the next level…usually recursion is used in many problems but sometimes it is very easy and efficient to solve the problem but sometimes in case of tail recursion it must be avoided…
you can take help from http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=recursionPt1
2 Likes
looking at the concept of recursion and the way the results are used, the typical data structure to use is ‘stack’.
in a way you can say that recursion = iteration with stack concept.
You should take some time and read these 2 wikipedia articles on recursion:
Always make sure your method will end in some point of time. My advice would be write the non-recursive statements first… For example for calculating factorial of a number (classic recursion example) you should begin with:
factorial(n)
if n==1 or n==0 return 1
This way you’ll know that at some point your method will return… And keep in mind that your method get to those values somehow:
factorial(n)
if n==1 or n==0 return 1
return n*factorial(n-1)
N will be decreasing by 1 when the methods are called, this means that at some point the method will be calculating factorial of 1 for sure. If you already know why I didn’t write an else block you can skip this part but basically it’s because when a return statement is reached the statements below it will not be executed … When a return statement is reached the method will end (this can be REALLY, REALLY HANDY sometimes)
Sometimes recursion can be really expensive therefore taking a lot of time to execute… Right now I can only remember 2 approaches to avoid this problem or at least make those methods less expensive:
Memoization: Basically it’s just store the values already calculated to avoid useless repetitions. For example:
factorials[]
// array with all values set to 0 (The length of the array depends on the problem one is solving)
factorials[0] = 1
factorials[1] = 1
// reminder: there isn't a number with factorial less or equal to zero
factorial(n)
if(factorials[n]>0) return factorials[n]
factorials[n] = n*factorial(n-1)
return factorials[n]
For very large numbers a lot of time can be saved using this approach, of course this is only an example, there are problems that show better the use of memoization
Another way to avoid expensive recursions is to not use recursions… Sometimes you can use arrays to store values without the aid of a recursive method. Even for calculating factorials or fibonacci sequence. This method usually requires some kind of pre-calculation. The problem DIAMOND is a very good example of how this method can be useful. Anyway here is an example of that using the factorial problem.
factorials[]
factorials[0] = 1
for i in 1 to factorials.length
factorials[i] = i*factorials[i-1]
//from here on just get the values from the array
All those methods have ups and down, with practice you’ll know which method to use for most problems
And you shouldn’t be looking for tutorials, look for exercises to solve, it’s the best way to learn… If you need help you can always count on codechef… So far it works for me hehe.
You shouldn’t be looking for tutorials, look for exercises to solve, it’s the best way to learn… If you need help you can always count on codechef both for exercises and support… So far it works for me hehe.
Ps.: Sorry for the long answer, sometimes I just let myself go 
1 Like