Iteration & Recursion

Iteration VS Recursion

1. Recursion

n! = n*(n-1)*(n-2)*(n-3)*...*1

The program can be directly written as:

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

Therefore, the computer has to keep track of the multiplications to be performed later on. This type of program, characterized by a chain of operations, is called recursion. Recursion can be further categorized into linear and tree recursion. When the amount of information needed to keep track of the chain of operations grows linearly with the input, the recursion is called linear recursion. The computer of n! is such a case, because the time required grows linearly with n. Another type of resursion, tree recursion, happens when the amount of information grows exponentially with the input.

2. Iteration

int factorial(int n){
    int product = 1;
    for(int i = 2;i<n;i++){
        product* = i;
    }
    return product;
}

This program, by contrast to program 2, does not build a chain of multiplication. At each step, the computer only need to keep track of the current values of the product and i. This type of program is called iteration, whose state can be summarized by a fixed number of variables, a fixed rule that describes how the variables should be updates, and an end test that specifies conditions under which the process should terminate. Same as recursion, when the time required grows linearly with the input, we call the iteration linear recursion.

3. Recursion VS Iteration

Compared the two processes, we can find that they seem almost same, especially in term of mathematical function. They both require a number of steps proportional to n to compute n!. On the other hand, when we consider the running processes of the two programs, they evolve quite differently.

In the iterative case, the program variables provide a complete description of the state. If we stopped the computation in the middle, to resume it only need to supply the computer with all variables. However, in the recursive process, information is maintained by the computer, therefore "hidden" to the program. This makes it almost impossible to resume the program after stopping it.