Waste less time on Facebook — follow Brilliant.
×

Exponential in Logarithmic Time : Recursive X Iterative

Take a look at this simple problem :

Compute \(a^b \mod m\)

The naive algorithm is \(O(n)\), which you multiply \(a\) by \(b\) times. However, most of you might be aware of the divide-and-conquer method which runs in \(O(\lg n)\) time complexity. The question is : recursive or iterative?

Many will say that recursion is a more natural way to think of, especially when dealing with Dynamic Programming, Segment Trees and Divide-and-Conquer algorithms. But recursive function is known to be slow, and I'll show you the actual runtime data.

Recursive algorithm :

1
2
3
4
long long f(long long a, long long b, long long m){
    if (b == 1) return a;
    return (f((a*a)%m, b>>1, m) * ( b&1 ? a : 1)) % m;
}

Iterative algorithm :

1
2
3
4
5
6
7
8
9
long long f(long long a, long long b, long long m){
    long long tmp = 1;
    while (b > 1){
        if (b&1) tmp = (tmp * a) % m;
        a = (a * a) % m;
        b >>= 1;
    }
    return (a * tmp) % m;
}

I've used some simple bit-manipulation techniques here. Fast explanation:

b & 1   // b % 2 == 1
b >> 1 // b / 2

No doubt that recursion is easier to understand and implement. But after some experiments, I got the runtime data for both algorithms. You can try generating your own input file to try it out.

generator

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
#include <bits/stdc++.h>

using namespace std;

#define MOD 1000000007

int main(){

    ofstream fout("input.txt");

    long long N = 5000000;

    fout << N << endl;
    for (long long i = 0; i<N; i++){
        srand(i);
        fout << rand() % MOD << " " << rand() % MOD << " " << rand() % MOD << endl;
    }

    return 0;
}

This is definitely not the best approach to generate test cases, as I don't have much experience in this, but it's enough for this problem.

The runtime is shown in the table below :

NRecursiveIterative
1,0000.010.00
10,0000.070.06
100,0000.280.25
1,000,0002.462.04
10,000,00024.0519.05

We can see that Recursion runs very slow compared to the iterative program when \(N\) is about \(10^7\). This is a concrete result. However, I couldn't find a reliable source on the reason about this. My best guess is that because it needs time to call a function, ie take the result and put it back to the previous recursion. Any ideas?

Note by Christopher Boo
10 months, 2 weeks ago

No vote yet
1 vote

Comments

Sort by:

Top Newest

You're spot on. There's overhead involved in calling a function, and when you do it thousands of time, that overhead adds up.

Consider the following program that simply recurses n times and then iterates n times. Compile and run this with optimizations turned off (because the example is so trivial, if optimizations are on, the recursion is tail call eliminated thus ruining the example).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <iostream>
#include <sys/time.h>

using namespace std;

uint64_t getmicros() {
    struct timeval now;
    gettimeofday(&now, NULL);
    uint64_t result = (uint64_t)now.tv_sec * (uint64_t)1e6 + now.tv_usec;
    return result;
}

int recurse(int n) {
    if (n == 0) {
        return 0;
    }
    else {
        return recurse(n - 1) + 1;
    }
}

int iterate(int v) {
    int result = 0;
    while (v > 0) {
        v -= 1;
        result++;
    }
    return result;
}

int main() {
    const int n = 262000;
    uint64_t start_time = getmicros();
    cout << recurse(n) << endl;
    uint64_t end_time = getmicros();
    cout << "Recursion took " << end_time - start_time << " microseconds." << endl;

    start_time = getmicros();
    cout << iterate(n) << endl;
    end_time = getmicros();
    cout << "Iteration took " << end_time - start_time << " microseconds." << endl;

    return 0;
}

(Note: if n is much bigger than 262000, I get a stack overflow on my machine. If this code immediately crashes for you when you run it, try reducing the size of n).

On my machine, this outputs:

1
2
3
4
262000
Recursion took 4049 microseconds.
262000
Iteration took 488 microseconds.

To call a function, roughly the following is done behind the scenes (you can see this if you look at the assembly): **

  1. The "current" function saves any registers it cares about to the stack.
  2. The "current" function pushes any parameters the "next" function needs to the stack.
  3. The "current" function yields control to the "next" function.
  4. The "next" function makes room on the stack for any local variables it might use.
  5. The "next" function does its job, reading the parameters from the stack, possibly calling other functions.
  6. When it's done, the "next" function either writes a return value to a predetermined location on the stack, or to a register.
  7. The "next" function then removes any local variables it used from the stack and passes control back to the "current" function.
  8. The "current" function restores its registers from the stack and reads the return value.

As you can imagine (and as the example shows), doing this thousands of times is much slower than just incrementing an integer in a loop.


** The exact details of this are dependent on the ABI of the language/compiler/architecture. Kristian Takvam Staff · 10 months, 1 week ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...