What is the difference between iteration and recur

问题:

What is the difference between iteration and recursion and why/when is one better:

while (true) {
    // Iterating
}

And

private void recursion() {
    if (true)
        recursion(); // Recursing

    return;
}

I see a lot of recursive implementation while it could be easily done in a simple loop.

回答1:

There are two main differences between Recursion and an Iterative Version of the same algorithm.

First of all, some times it is almost better to understand a recursive algorithm than an iterative one (At least if you are experienced programmer) So it does increase expressivity and in some cases readability (It might also lead to the exact opposite in other cases)

Expresivity is a huge deal on programming languages and be able to write the same code in 5 lines instead of 20 is a huge deal.

On the downside, it decreases the performance of your code. Recursive functions have to keep the function records in memory and jump from one memory address to another to be invoked to pass parameters and return values. That makes them very bad performance wise.

Sum Up:

Iterative Algorithms = Fast Performance but hard to write (sometimes hard to read too)

Recursive Algorithms = Fast to write but Bad performance wise (Sometimes easier to understand too)

Take this example:

public static long fib(long n) {
    if (n <= 1) return n;
    else return fib(n-1) + fib(n-2);
}

vs

    if ((n == 1) || (n == 2)) {
        return 1;
    } else {
        long prev = 1, current = 1, next = 0;
        for (long i = 3; i <= n; i++) {
            next = prev + current;
            prev = current;
            current = next;
        }
        return next;
    }

Source:

http://www.csd.uwo.ca/Courses/CS1027a/code/FibonacciDemo.java

回答2:

The main difference between recursion and iteration is memory usage.

For every recursive call needs space on the stack frame resulting in memory overhead.

Let me give you an example. Imagine in one case you forgot to write the base case for your recursive function resulting in endless recursive calls and in other case you wrote an infinite loop.

Since every recursive function assigns new memory space, in first case your code will give a stack overflow exception but in second case it will keep running forever.

So it better to make your iterative code more understandable than using Recursion.

回答3:

They are different ways to do the same thing. All recursive implementations can be done with a (or multiple) loop(s) and vise versa. It is more about the logic behind it, a way to think about it. Factorial, although not the best example, is n * (n-1)! so it makes sense to use it recursively.

回答4:

Recursion and iteration are different ways to think about a solution. It would be dificult to explain in depth the difference in full scope. In your sample code, you aleady showed the difference. Recursive function is the one that calls itself, while iterative is the one that loops through some block of code. Here are some articles to help you understand them better: Recursion wiki

Iteration wiki

CodeProject SO #1

SO #2

回答5:

In theory, you can always swap between iteration and recursion. However, at least in case of C/C++/C#/Java, the compiler offers you some support which might make the solution more elegant, especially when you don't know the number of loops before.

The best example is listing all the files inside a folder and it's descendants. If there are several subfolders containg subfolders, normaly in iteration mode you need a stack to save all folders you need to analyze. In case of recursive approach, the stack is already provided by the compiler, and the solution is more elegant.

回答6:

They can be used interchangeable to solve different problems. In essence you can write recursive functions iteratively and vise versa.

Iteration may increase the performance of your program. Whereas recursion may give a more intuitive and elegant result. You can choose either which to your preference!

回答7:

Recursive functions work through the process of calling themselves until a condition is met whereas iteration uses a looping control structure (for example while, do while, for) in order to repeat a section of code until a certain condition is met.

Recursive example:

int rec_func(int u, int k) {
  if (k == 0)
    return u;
  return rec_func(u * k, k - 1);
}

Iteration example:

int ite_func(int u, int k) {
  while (k != 0) {
    u = u * k;
    k = k - 1;
  }
  return u;
} 

The only real difference IMO between them is compilation differences.

回答8:

Differences between recursion and iteration

Recursion

1. Recursive function – is a function that is partially defined by itself
2. Recursion uses selection structure
3. Infinite recursion occurs if the recursion step does not reduce the problem in a manner that converges on some condition (base case)
4. Recursion terminates when a base case is recognized
5. Recursion is usually slower than iteration due to overhead of maintaining stack
6. Recursion uses more memory than iteration
7. Infinite recursion can crash the system
8. Recursion makes code smaller

Iteration

1. Iterative Instructions – are loop based repetitions of a process
2. Iteration uses repetition structure
3. An infinite loop occurs with iteration if the loop condition test never becomes false
4. Iteration terminates when the loop condition fails
5. Iteration does not use the stack so it's faster than recursion
6. Iteration consumes less memory
7. Infinite looping uses CPU cycles repeatedly
8. Iteration makes code longer

Data taken from here.