What are the Differences between Recursion and Iteration

02/27/2022 Tags: C_C_plus_plus Programming

[2022/06/16]

Brief

Iteration and recursion are key computer science technique using in developing algorithm and programming. In simple terms, an iterative function is one that loops to repeat some part of the code, and a recursive function is one that calls itself again to repeat the code. Both of two terms repeatedly execute the set of instructions. In this post, I would like to record a few pieces of information for avoiding to forget bit and pieces and also hope to be helpful.

The Basic Concept of Recrusion and Iteration

Recrusion

The distinctive feature of a recursive function is that, when called, it may result in more calls to itself. For a simple example, here is the calculation of factorial function by recrusion:

double Factorial(int n)
{
    double factorial;
    if (n == 0) factorial = 1;
    else factorial = n * Factorial(n -1);
}

Each time factorial function is called recursively, a new level of recursion is created. To be specific, whenever you call a function, including recursively. the return address and often the arguments are pushed onto the call stack.

However, the stack is finite, so if the recursion is too deep you’ll eventually run out of stack space and see an error message saying something like “Function call stack overflow”.

Note that:

The command “ulimit -s” could display the size of the stack is configurble on Unix.
Given that the function is tail-call recursion, some compilers might be able to optimize the recursive call away by turning it into a jump.

Iteration

Iteration is when the same procedure is repeated multiple times. There are two types of iterative loops: for-loop and while-loop. For a simple example, here the the calculation of factorial function by for-loop interation:

int main(int argc, char *argv[])
{
    auto start = chrono::steady_clock::now();

    double factorial = 1;

    for (int i = 0; i < 10000; ++i) {
        factorial = factorial * i;
    }
}

Iteration use repetition structure and does not use the stack so it’s faster than recursion and the memory allocation is less than that of an recursion function.

Analysis of Runtime between Recrusion and Iteration

$ ./factorial
Iteration: Elapsed time in nanoseconds: 34325 ns
Recursion: Elapsed time in nanoseconds: 370471 ns

Simple Example: pow(x, n)

Implement pow(x, n), which calculates x raised to the power n (i.e., x^n).

Iteration:

iteration_power.cc

double myPow(double x, int n) {
    int flag = 0;
    double res = 1;
    if( n < 0 )
    {
        flag = 1;
        n = abs(n);
    }
    while( n > 0 )
    {
        if( n & 1 )
            res = res*x;
        x = x*x;
        n >>= 1;
    }
    if(flag)
        res = 1/res;
    return res;
}

Recrusion:

recrusion_power.cc

double myPow(double x, int n) {
    if (n == 0) return 1;
    if (n<0) return 1/x * myPow(1/x, -(n+1));
    if (n%2 == 0) return myPow(x*x, n/2);
    else return x*myPow(x*x, n/2);
}

Now, as you can see, the recursion approach is executed much slowerly than iteration approach.

=========== To be continued…. ==========