How to think in recursive way?

Question

In order to understand the advanced algorithm concepts like greedy methods and dynamic programming, one first need to be well versed in recursion.

I am relatively new to recursion. Whenever a question is asked, the first things that pops up in mind are solutions using iterations. Even though I know what recursive methods means and how it works, it is very difficult to think in a recursive way.

Please help out by answering the below questions:

1) Can any iterative method be replaced by recursion and vice versa?

For example, how to print elements in an array of size n recursively?

for i 0 to n
 Print a[i]

2) How to solve a problem recursively? What are the steps? Is there any tips to identify that a problems can be solved recursively?

For ex: If am asked to print out all the sub strings of a string

INPUT: CAT
OUTPUT: CAT,CA,A,AT,T

I can come up with an iterative way fast.Using two loops can solve the problem.

But recursively how to solve it.How to identify that a problems can be solved recursively.

If answer to my first question is yes, using two recursions instead of iteration can be solution to my problem?

3) Can anyone suggest me some materials/resources to understand the concept of recursion thoroughly?

Answer 1

There is a way of thinking about recursion that makes it as easy as iteration.

In iteration we have a loop. Think of it as having 4 parts:

1. A decision to continue or stop, based on some "controlling" data, evaluated as a logical condition.

2. A body, where the work is done. Sometimes, the body is combined with the next part.

3. A way of changing the "controlling" data. Often by changing a counter.

4. A way of invoking the construct (in this case, the loop) again. In c-style languages this is provided by the for, while, or do syntax.

In recursion we have a function (sometimes several). They have the same 4 parts:

1. A decision to continue or stop, based on some "controlling" data, evaluated as a logical condition. The controlling data is usually passed to the function as parameter(s).

2. A body, where the work is done. Sometimes, the body is combined with the next part.

3. A way of changing the "controlling" data. Often by changing a counter.

4. A way of invoking the construct (in this case, the function) again - that means call the function (and remember to pass the changed "controlling" data.

It should be of no surprise that the two constructs have the same parts, since they are equivalent.

Answer 2

1. Yes, principally. In general recursion is done for the programmer's sake, not the computer's. There are iterative methods that in some cases may run faster than recursive ones, but the iterative method may take 300 lines of code and the recursive 3. There are also some cases where it's easy to figure out how to program something recursively, but is very difficult to write iteratively and vice versa.

2. Generally the recursive solution needs to be though of in terms of the function. If we're using something like C++, we can use a solution dealing with string references and things, slowly adjusting the strings being passed as parameters. The point near the end of "two recursions" is misguided though. The principle here is that instead of two iterations, we can do one recursive approach.

3. http://introcs.cs.princeton.edu/java/23recursion/ this site (high up on the google search) teaches a lot of the math theory of recursion and includes a FAQ which may give you a more satisfying answer to number one.