Recursive vs iterative approach

Avichal

Maybe this question better belongs to programming section but I feel it has mathematics related doubt.

I want an intuition on how iterative and recursive approaches are different. Just look at the simple arithmetic progression. n^th term is given as a + n.d. This can be derived using both iterative and recursive methods.
I am looking for the basic idea behind both the approaches.
Also can all recursive solution be converted to iterative solution? In Fibonacci sequence can n^th term be found iteratively?

So if all iteraitve and recursive solutions be interconvertible whats the basic difference between both, i mean the basic crux or logic behind both?
Ah, I still feel I couldn't convey my question!

Vorde

I can try to answer.

Basically a recursive algorithm calculates a number then uses the number it just calculated to calculate the next number, and so on. An iterative algorithm is a algorithm which 'calls' itself at some point in it's progression.

The fibonacci sequence is a really good example of this. You can write functions (I'm assuming you know some basic programming - stop me if I'm off) that calculate terms in the Fibonacci sequence, store those terms as variables, and use that variable to compute the next term; this is a recursive approach.

You can also write a function which seems to be doing the same thing but instead of storing a number as a variable the function calls itself. Meaning at some line in a int Function() you would have a call to int Function(), a.k.a a call to itself. This creates a nested function within a function that can be evaluated to produce terms in the Fibonacci sequence. This is an iterative approach.

I have to run or else I would show the code in both these cases. If no one else has answered your question better later I can edit in some stuff.

rcgldr

Quote by Vorde

Basically a recursive algorithm calculates a number then uses the number it just calculated to calculate the next number, and so on. An iterative algorithm is a algorithm which 'calls' itself at some point in it's progression.

For computer science (programming), an interative approach is one that uses one or more loops within a function, while a recursive approach is one where a function calls itself. Wiki article:

wiki_recursion_cs.htm

A recursive approach can be converted into an iterative approach by using an array to replace the functionality of the stack. In some cases, there may be an naturally iterative approach that can be used instead of a recursive approach.

An iterative approach can be converted into a recursive approach by passing all the loop related variables as parameters to a self called function, but this is usually inefficient.

*Studiot*

My trusty maths dictionary (this is the maths forum, not the programming one) says that they mean the same thing.

iterative : (adjective) : Another word for recursive.

Vorde

Ah! I apologize, I mixed up the terms. Idiotic on my part, sorry OP.

My C++ book literally starts the chapter on recursion with "A recursive function in C++ is a function that calls itself."
Should have checked before I posted.

Sorry :)

rcgldr

Quote by Studiot

My trusty maths dictionary (this is the maths forum, not the programming one) says that they mean the same thing.

In the case of math, the definitions overlap. Wiki articles mentions that recursion repeats in a self-similar way:

http://en.wikipedia.org/wiki/Iteration

http://en.wikipedia.org/wiki/Recursion

For computer science (programming), the terms have different meanings as explained above: iteration means looping, recursion means a function that calls itself.

Example of converting a recursive approach to an interative approach.

iterative_recursion.htm

Quote by Avichal

In Fibonacci sequence can n^th term be found iteratively?

Yes, link to example progam:

fibonacci_iterative.htm

haruspex

In software, the difference is essentially that they work from opposite ends. In iteration, you start with an almost trivial case and solve it; then using that you can solve the next case. In recursion, you start from the endpoint and reason that you could solve that if you knew the answer to the next simpler case - so you go off and solve that then return to complete the job.
The advantage of recursion is elegance. Take the towers of Hanoi problem. It's easy to see that a solution is:
To move the top N discs from tower A to tower B
- move the top N-1 from tower A to tower C
- move the top disc from A to B
- move the top N-1 from C to B
Once you've observed that is a solution, it's quite easy to restructure it as iteration, but either way it takes 2^N steps.
Fibonacci, OTOH, demonstrates a serious disadvantage of recursion. The number of steps required is again exponential (equal roughly to the value that will be computed). But the iterative solution only takes N steps.
Another disadvantage of recursion is stack size, which can be hard to anticipate.

In theoretical computing and some related fields, recursive definitions arise. E.g. in the definition of a statement in a given computer language. Not sure how you'd replace those with a form of iteration. In consequence, the compiler likely analyses the program recursively, but I couldn't swear to that.

In mathematical induction, I don't see a distinction. You have the inductive step and the base case, but whether you think of the proof as running backwards to or forwards from the base case is a matter of taste.
There is a trap using recursion in mathematical definitions. If you attempt to use the definition to assess whether an object satisfies it, you could find yourself in infinite regress. You need some way of ensuring that the recursive analysis terminates for any given object - otherwise the definition is broken.

Edgardo

I recommend looking at the factorial function. It can both be implemented iteratively and recursively.

As already mentioned iteration involves using for loops. The recursive approach uses a function that calls itself.
This sounds a little strange but let's have a look at how 3! is calculated:

1. iteration:
Simply calculate 1*2*3

Code:

result = 1
for(i=1 to 3):
     result = result*i

print result

2. recursion:
The recursive function is defined as:

Code:

f(1)=1   
f(n) = n*f(n-1)

Plug in n=3:
f(3) = 3*f(3-1) = 3*f(2)

What is f(2)?
f(2) = 2*f(2-1) = 2*f(1)

What is f(1)?
f(1) = 1, according to definition

Let's write everything in succession:
f(3)
= 3*f(2)
= 3*(2*f(1))
= 3*(2*(1))

*Studiot*

These comments are true if you actually (intend to) carry out all the steps.

It is often possible, however, to develop a formula for the nth term without this effort.

AlephZero

Quote by haruspex

Fibonacci, OTOH, demonstrates a serious disadvantage of recursion. The number of steps required is again exponential (equal roughly to the value that will be computed). But the iterative solution only takes N steps.

That's true for a simple implementation of recursion, but there are ways round it. One improvement is to remember everything you already calculated, so you don't have to calculate it again. For example to calculate the 10th Fibonacci number, you have
f(10) = f(9) + f(8) ... (*)
So you start by calculating f(9)
f(9) = f(8) + f(7), etc

But after you have done that, you already know the value of f(8) to finish calculating Eq. (*), so you don't need to calculate f(8) again.

This is a very powerful idea in situations where you can't easily analyze the complete algorithm in advance to figure out what you need to calculate. An example would be a chess program looking at possible future moves, There are often many different ways of getting to the same position on the board, but the "history" of how you got there is irrelevant to how good the position is. (OK, that's a slight simplification of the real rules of chess, to simplfy the example!)

rcgldr

Quote by haruspex

Fibonacci, OTOH, demonstrates a serious disadvantage of recursion.

Quote by AlephZero

That's true for a simple implementation of recursion, but there are ways round it. One improvement is to remember everything you already calculated

Such as an array FIB[] to hold the fibonacci numbers, initialized to zero so that if(FIB[k] != 0) would indicate FIB[k] was previously calculated. Even with this improvement, there's still the additional call and stack overhead versus the iterative method for fibonacci numbers.

- - -

Perhaps a better example for using recursion would be navigation of a tree like structure, such as the files and folders in a partition. Assume the goal is to process all files in the current directory first, then to recursively process all sub-directories in the current directory. There are two main loops, one to process files, the other to process sub-directories. Iteration would be awkward since the recursion returns back into the middle of the second loop. The code would look something like this:

Code:

typedef _DIR{   // directory structure
_DIR * pnext;   //  ptr to next entry
_DIR * psubdir; //  ptr to sub-directory
                //    or NULL if file
// ...          //  directory entry data
}DIR;

void ProcessFile(DIR * pdir); // ...

void ProcessDirectory(DIR * pdir)
{
DIR *pent; // used to scan entries in pdir

    pent = pdir;
    while(pent){
        if(pent->psubdir == NULL) // if file
            ProcessFile(pent);
        pent = pent->next;
    }

    pent = pdir;
    while(pent){
        if(pent->psubdir != NULL) // if sub-dir
            ProcessDirectory(pent->psubdir);
        pent = pent->next;
    }
    return;
}

Best Pokemon

You can use recurrence relations for recursion.

Avichal

Why is recursion sometimes easier that iteration. Programs like n-queens and knights tour are easy using recursion but I struggle making them using iteration.

So what advantage does recursion offer in such cases. Why its easier to think recursive in some cases?

D H

Quote by haruspex

Fibonacci, OTOH, demonstrates a serious disadvantage of recursion. The number of steps required is again exponential (equal roughly to the value that will be computed).

That depends on how you code the recursive solution. The naive implementation is exponential. The following recursive implementation only takes N recursive calls, and since it's a tail recursive algorithm, most compilers will optimize away the recursion. In C++,

Code:

#include <iostream>
#include <stdint.h>

uint64_t fibonacci_helper (uint64_t N, uint64_t prev, uint64_t curr)
{
   return (N == 0) ? curr :  fibonacci_helper (N-1, curr, prev+curr);
}

uint64_t fibonacci (uint64_t N)
{
   return (N == 0) ? 0 : fibonacci_helper (N-1, 0, 1); 
}

int main ()
{
   std::cout << "Fib(20) = " << fibonacci(20) << "\n";
   std::cout << "Fib(93) = " << fibonacci(93) << "\n";
   return 0;
}

With C++ you can also use templates to get an O(1) runtime solution:

Code:

#include <iostream>
#include <stdint.h>

template<uint64_t N>
struct template_fibonacci {
   enum {
      value = template_fibonacci<N-2>::value + template_fibonacci<N-1>::value
   };
};

template<> struct template_fibonacci<0> { enum { value = 0ull }; };
template<> struct template_fibonacci<1> { enum { value = 1ull }; };

int main ()
{
   std::cout << "Fib(20) = " << template_fibonacci<20>::value << "\n";
   std::cout << "Fib(93) = " << template_fibonacci<93>::value << "\n";
   return 0;
}

Note that this uses the simple version of the recursive Fibonacci algorithm. The upside is that the compiler automagically does the memoization (what AlephZero wrote about in post #10). The downside is that you can't compute template_fibonacci<N>::value where N is a runtime integer.

rcgldr

Quote by rcgldr

An iterative approach can be converted into a recursive approach by passing all the loop related variables as parameters to a self called function, but this is usually inefficient.

Quote by D H

The following recursive implementation only takes N recursive calls, and since it's a tail recursive algorithm, most compilers will optimize away the recursion. In C++

Code:

#include <iostream>
#include <stdint.h>

uint64_t fibonacci_helper (uint64_t N, uint64_t prev, uint64_t curr)
{
   return (N == 0) ? curr :  fibonacci_helper (N-1, curr, prev+curr);
}

uint64_t fibonacci (uint64_t N)
{
   return (N == 0) ? 0 : fibonacci_helper (N-1, 0, 1); 
}

This seems very similar to An iterative approach can be converted into a recursive approach by passing all the loop related variables as parameters to a self called function ... , where recursion is just being used as a loop mechanism, and the stack is filled with instances of the iterated values. fibonacci() and fibonacci_helper() could be translated into this iterative code:

Code:

    if(N == 0)       // fibonacci()
        return(0);
    prev = 0;
    curr = 1;
    N = N - 1;

    while(N != 0){  // fibonacci_helper()
        sum = curr + prev;
        prev = curr;
        curr = sum;
        N = N - 1;
    }

D H

Quote by rcgldr

Quote by D H

Code:

#include <iostream>
#include <stdint.h>

uint64_t fibonacci_helper (uint64_t N, uint64_t prev, uint64_t curr)
{
   return (N == 0) ? curr :  fibonacci_helper (N-1, curr, prev+curr);
}

uint64_t fibonacci (uint64_t N)
{
   return (N == 0) ? 0 : fibonacci_helper (N-1, 0, 1); 
}

This seems very similar to An iterative approach can be converted into a recursive approach by passing all the loop related variables as parameters to a self called function ... , where recursion is just being used as a loop mechanism, and the stack is filled with instances of the iterated values.

I like to look at it the other way around: That a tail recursive algorithm can be converted to an iterative algorithm. That's what a good optimizing compiler for C or C++ is going to do. However, C and C++ are not the only languages in the world. In a functional language such as Lisp or Haskell, the underneath the hood implementation of an iterative algorithm is to convert it to a recursive one.

Here's one more recursive implementation of the Fibonacci algorithm. Note this is not tail recursive.

Code:

uint64_t fibonacci (
   uint64_t N)
{
   if (N == 0) {
      return 0;
   }   
   else if (N == 1) {
      return 1;
   }   
   else {
      uint64_t k = N >> 1;
      uint64_t f1 = fibonacci(k);
      uint64_t f2 = fibonacci(k-1);

      if ((N & 1ull) == 0ull) {
         return f1 * (f1 + f2 + f2);
      }   
      else if ((N & 3ull) == 1ull) {
         return (f1 + f1 + f2) * (f1 + f1 - f2) + 2ull;
      }   
      else {
         return (f1 + f1 + f2) * (f1 + f1 - f2) - 2ull;
      }   
   }   
}

The above is an O(N) algorithm, same as the tail recursive version. Add memoization to the above and you get an O(log(N)) algorithm.

rcgldr

Quote by D H

I like to look at it the other way around: That a tail recursive algorithm can be converted to an iterative algorithm.

OK. My issue was that all the iterated variables (prev, curr, prev+curr) were being passed as parameters, so it didn't seem that recursion was accomplishing much with that implementation of fibonacci, plus it added the overhead of pushing all instances of those iterated vairable onto the stack (assuming a compiler didn't convert it to an iterative algorithm).

Quote by D H

Here's one more recursive implementation of the Fibonacci algorithm. Note this is not tail recursive.

This one is better although a bit more complex, although again it seems a similar approach could be done iteratively.

I think the directory / nodal tree scan example from my earlier post is a better case for using recursion than fibonacci. Fibonacci can be easily implemented iteratively, but the two loop (1st loop for files / leaves, 2nd loop for sub-directories / sub-nodes) directory / tree scan, is awkward to implement iteratively, depending on the language (in C, it requires a goto to jump into the middle of the 2nd loop when the end of the current directory / branch is reached, in addition to restoring pointers / variables to the next "higher" directory / node).

Similar Threads for: Recursive vs iterative approach
Thread	Forum	Replies
Iterative method	Precalculus Mathematics Homework	3
Which approach is nicer? UK MEI approach? American approach?	Academic Guidance	0
iterative map in mathematica	Math & Science Software	5
Iterative Methods	Calculus & Beyond Homework	6
Iterative routines	General Math	13

Vorde Recognitions: Gold Member	Ah! I apologize, I mixed up the terms. Idiotic on my part, sorry OP. My C++ book literally starts the chapter on recursion with "A recursive function in C++ is a function that calls itself." Should have checked before I posted. Sorry :)

Studiot	These comments are true if you actually (intend to) carry out all the steps. It is often possible, however, to develop a formula for the nth term without this effort.

Avichal	Why is recursion sometimes easier that iteration. Programs like n-queens and knights tour are easy using recursion but I struggle making them using iteration. So what advantage does recursion offer in such cases. Why its easier to think recursive in some cases?