Iteration vs Recursion

June 23, 2019

In programming, iteration, and recursion are methods to solve problems. Now, I cover these two methods, gave a simple explanation then solve some common problems in a programming interview as examples.

Iteration

Iteration is a repetition of a process based on loop. Technically, using for or while.

Recursion

Recursion is a method that calls itself for a repetition.

Examples

I wrote all examples in C. All problems are solved both in the iterative and recursive method.

Factorial

Factorial (symbol: !) is multiplying all whole numbers from the chosen number down to 1.

unsigned int factorial_iterative(unsigned int n) {
    int result = 1;
    
    for (int i = n; i > 0; i--) result *= i;
    
    return result;
}

unsigned int factorial_recursive(unsigned int n) {
    if (n == 0) return 1;
    return n * factorial_recursive(n - 1);
}

Fibonacci

Fibonacci (symbol: F_n) is an integer sequence that each number is the sum of the two proceeding ones.

int fibonacci_iterative(int n) {
    if (n <= 1) return n;
    
    int result = 1;
    int less_one = 0;
    int less_two;
    
    for (int i = 2; i <= n; i++) {
        less_two = result;
        result += less_one;
        less_one = less_two;
    }
    
    return result;
}

int fibonacci_recursive(int n) { 
    if (n <= 1) return n; 
    return fibonacci_recursive(n - 1) + fibonacci_recursive(n - 2); 
}

Reverse String

Reverse String is a common question in a programming interview. Example, "abc123" to be "321cba".

void reverse_string_iterative(char *string, int start, int end) { 
    int tmp;
    
    while (start < end) { 
        tmp = string[start];    
        string[start] = string[end]; 
        string[end] = tmp;
    
        start++;
        end--; 
    }    
}

void reverse_string_recursive(char *string, int start, int end) {
    if (start >= end) return;
    
    int tmp; 
    
    tmp = string[start];    
    string[start] = string[end]; 
    string[end] = tmp;
    
    reverse_string_recursive(string, start + 1, end - 1);
}

Conclusion

Exactly, there are still some examples that I want to bring them here. I only want to make it faster. So, three examples are enough to make an understanding of iteration and recursion.

I still remember when I was with my friends, we tested the performance of the method of iteration and recursion. The recursion is slow, even if it makes the code smaller.

Focus on performance when making a solution. That is why I prefer an iteration method.