How to think in recursive way?

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:

Source : interactivepython

Another program in Javascript to find factorial:

function factorial(n){
    if (n == 1)
        {
        return 1;
        }
    else {
        return n * factorial(n-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.
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.
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.

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:

A decision to continue or stop, based on some "controlling" data, evaluated as a logical condition.
A body, where the work is done. Sometimes, the body is combined with the next part.
A way of changing the "controlling" data. Often by changing a counter.
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:

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).
A body, where the work is done. Sometimes, the body is combined with the next part.
A way of changing the "controlling" data. Often by changing a counter.
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.

Related