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?

Hermilahermina

You have a bag of letters and a street of houses. Do you say "for each house, check letters at top of pile, and deliver, then go on to next house" or do you say, "deliver first set of letters to first house in the street, remove that house from the street, and repeat until the street has no houses"? – Tireless

Not each problem makes sense in recursion - printing elements from an array is a good example, this is better suited for pure iteration. Prinitng elements from a multidimensional array might be better suited for a recursive approach – Shell

I wrote a post on this recently: mfaani.com/posts/interviewing/how-to-think-recursively-part1 – Patterman

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.

Glade

this is an interesting way to think of these two concepts and relate them! thanks for sharing! – Heddy

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.

Borges

Thanks for the Answer.Could you please explain how to print all the elements in an array recursively? – Hermilahermina

Basically, we set up a function with an input parameter, then we call this same function on less of the input, in the case of CAT, we call it on CAT, then we call it on CA, then C, then A, followed by calling it on AT, then A, then T. The reason it's called in this order, is because that's how the recursive code would work. We'd also implement a check to prevent A from being printed twice, by simply checking against the output data structure. – Borges

@RahulKurup I gave the answer. – Seychelles

Answer 3

Let's take a simple task. Printing numbers from 1 to 10. I'll use Python2.7 here.

for i in range(1,11):
    print i

Now let's try to do the same, using recursion.

>>> def print_me(n):
    if n > 0:
        print_me(n - 1)
        print n
    else:
        return

>>> print_me(10)
1
2
3
4
5
6
7
8
9
10

So how do we think of it ?

• Step1: Think of my boundaries. I need two . 1 and 10. Next.
• Step2: The print statement. That's our motive. To print numbers. And we want it from 1 to 10. So I need to print 1 first.

• Step3: We start by writing a function that does the job of printing a number passed as an argument. Let's think of just, the main task.

  def print_me(n): print n

• Step 4: I want the function to return, if n < 1.

  def print_me(n): if n > 0: print n else: return

• Step 5: Now I want to pass numbers, from 1 to 10 to this function, but we don't want a loop of 1 to 10 , and then pass it to our function. We want it to be done recursively.

What is recursion? In plain words, the repeated application of a recursive procedure or definition.

So in order to make it recursive, we need to call the function itself. And we want to pass our range of 1 to 10.

def print_me(n):
    if n > 0:
        print_me(n - 1)
        print n
    else:
        return

Summarizing: All recursive calls must obey 3 important rules:

1. A recursive algorithm, MUST have a base case.
2. A recursive algorithm, MUST change its state and move toward the base case.
3. A recursive algorithm MUST call itself, recursively.

Source : interactivepython

Another program in Javascript to find factorial:

function factorial(n){
    if (n == 1)
        {
        return 1;
        }
    else {
        return n * factorial(n-1);
        }
}

Marv

Answer 4

@Test
public void testStrings() {
   TreeSet<String> finalTree = getSubStringsOf("STACK");
    for(String subString : finalTree){
        System.out.println(subString);
    }
}

public TreeSet<String> getSubStringsOf(String stringIn) {
    TreeSet<String> stringOut = new TreeSet<String>();
    if (stringIn.length() == 1) {
        stringOut.add(stringIn);
        return stringOut;
    } else {
        for (int i = 1; i < stringIn.length() ; i++) {
            String stringBefore = stringIn.substring(0, i);
            String stringAfter = stringIn.substring(i);
            stringOut.add(stringBefore);
            stringOut.add(stringAfter);
            stringOut.addAll(getSubStringsOf(stringBefore));
            stringOut.addAll(getSubStringsOf(stringAfter));
        }
        return stringOut;
    }
}

I don't know if you need explanation. You split the string in two every time it's possible. Cat is thus split into CA,T and C,AT, you add them to your list of substring, then look for every substring of these substrings. If the String is a single character, you add the single character to your tree.

EDIT: this is the output for STACK:

A AC ACK C CK K S ST STA STAC T TA TAC TACK

EDIT again: As you can see, every time you run the method subString,you'll use it twice inside it, except if it's a single character String. Thus the complexity is O(n²). For 'STACK', the program is 0.200 ms long, for "STACKSTACKSTACK" (3 times stack) is 2seconds, for "STACKSTACKSTACKSTACKSTACK" is theoritically 2^10 times more, thus 2000 seconds.

Seychelles

Answer 5

Here is my simple test in Python:

def p(l, index):
    if index == len(l):
        return
    else:
        print l[index]
        index = index + 1
        p(l, index)

and call:

p("123456", 0)

Breeches

Answer 6

Here's the code to print the array recursively in c++

#include<iostream>
using namespace std;

void print(int arr[],int n)
{
if(n==0)     //base case. function call hits the base case when n==0
{
cout<<arr[0]<<" ";
return;
}
print(arr,n-1);   //function will be called recursively until it reaches the 
                    base case.
cout<<arr[n]<<" ";
}
              //Driver function
int main()
{
int arr[]={10,20,30,40,50}; //array has been initialized with values 
                                               // 10,20,30,40,50 

int n=sizeof(arr)/sizeof(arr[0]) ; //n stores the size of array,i.e, n=5; 
print(arr,n-1);   //print function has been called with arr[] and (n-1) as 
                    parameters.
return 0;
}

I hope it helps in some manner

Barbershop

Please add some explanation to your code such that others can learn from it – Shell

Please don't encourage the use of #include<bits/stdc++.h>! See: here. – Lemus

Thanks, Adrian for letting me know, I've been using it mostly while doing competitive programming, it is more of a time saving and efficient way in competitions though. – Barbershop

Answer 7

The CAT problem can be solved like this : (Python code)

s = "CAT"
op = []
def sub(s):
    # terminating condition.
    if (len(s) == 0) : return

    if s not in op : op.append(s)
    
    # slices from begning
    sub(s[1:])
    # slices from the end
    sub(s[:-1])

sub(s)
print(op)

Output : ['CAT', 'AT', 'T', 'A', 'CA', 'C']

Aldis

Answer 8

I think we can solve any iterative problem using recursive function, however it might not be the most effecient approach. Here is a simple example for printing items in a list using both "for loop" and "recursive" in Python3:

a = [ 1,2,3,4,5] 
#iterative approach using a for loop
for i in nums:
   print(i)

#recursive approach
def printing_list(nums):
    #base case
    if len(nums)==0:
        return
    #recursive
    else:
        print(nums[0])
    return printing_list(nums[1:])

printing_list(nums)

To think recursively, it might be best to write the for loop first and then try to write the recursive solution based on that. remember all recursive approaches need a base case to stop the recursive

Tilley