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.