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 :

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 :

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

#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 :

N	Recursive	Iterative
1,000	0.01	0.00
10,000	0.07	0.06
100,000	0.28	0.25
1,000,000	2.46	2.04
10,000,000	24.05	19.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?

Markdown

Appears as

*italics* or _italics_

italics

**bold** or __bold__

bold


- bulleted
- list

bulleted
list


1. numbered
2. list

numbered
list

Note: you must add a full line of space before and after lists for them to show up correctly

paragraph 1

paragraph 2

paragraph 1

paragraph 2

[example link](https://brilliant.org)

example link

> This is a quote

This is a quote

    # I indented these lines
    # 4 spaces, and now they show
    # up as a code block.

    print "hello world"

# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"

Math

Appears as

Remember to wrap math in $ ... $ or \[ ... \] to ensure proper formatting.

2 \times 3

2 \times 3

2^{34}

2^{34}

a_{i-1}

a_{i-1}

\frac{2}{3}

\frac{2}{3}

\sqrt{2}

\sqrt{2}

\sum_{i=1}^3

\sum_{i=1}^3

\sin \theta

\sin \theta

\boxed{123}

\boxed{123}

#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; }

Easy Math Editor

This discussion board is a place to discuss our Daily Challenges and the math and science related to those challenges. Explanations are more than just a solution — they should explain the steps and thinking strategies that you used to obtain the solution. Comments should further the discussion of math and science.

When posting on Brilliant:

Use the emojis to react to an explanation, whether you're congratulating a job well done , or just really confused .
Ask specific questions about the challenge or the steps in somebody's explanation. Well-posed questions can add a lot to the discussion, but posting "I don't understand!" doesn't help anyone.
Try to contribute something new to the discussion, whether it is an extension, generalization or other idea related to the challenge.
Stay on topic — we're all here to learn more about math and science, not to hear about your favorite get-rich-quick scheme or current world events.

Markdown	Appears as
`italics` or `_italics_`	italics
`bold` or `__bold__`	bold
- bulleted - list	bulleted list
1. numbered 2. list	numbered list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1 paragraph 2	paragraph 1 paragraph 2
`[example link](https://brilliant.org)`	example link
`> This is a quote`	This is a quote
# I indented these lines # 4 spaces, and now they show # up as a code block. print "hello world"	# I indented these lines # 4 spaces, and now they show # up as a code block. print "hello world"

Math	Appears as
Remember to wrap math in `$` ... `$` or `\[` ... `\]` to ensure proper formatting.
`2 \times 3`	$2 \times 3$
`2^{34}`	$2^{34}$
`a_{i-1}`	$a_{i-1}$
`\frac{2}{3}`	$\frac{2}{3}$
`\sqrt{2}`	$\sqrt{2}$
`\sum_{i=1}^3`	$\sum_{i=1}^3$
`\sin \theta`	$\sin \theta$
`\boxed{123}`	$\boxed{123}$

Comments

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).

(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:

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): **

The "current" function saves any registers it cares about to the stack.
The "current" function pushes any parameters the "next" function needs to the stack.
The "current" function yields control to the "next" function.
The "next" function makes room on the stack for any local variables it might use.
The "next" function does its job, reading the parameters from the stack, possibly calling other functions.
When it's done, the "next" function either writes a return value to a predetermined location on the stack, or to a register.
The "next" function then removes any local variables it used from the stack and passes control back to the "current" function.
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 - 5 years, 4 months ago

Math	Appears as
Remember to wrap math in `\(` ... `\)` or `\[` ... `\]` to ensure proper formatting.
`2 \times 3`	$2 \times 3$
`2^{34}`	$2^{34}$
`a_{i-1}`	$a_{i-1}$
`\frac{2}{3}`	$\frac{2}{3}$
`\sqrt{2}`	$\sqrt{2}$
`\sum_{i=1}^3`	$\sum_{i=1}^3$
`\sin \theta`	$\sin \theta$
`\boxed{123}`	$\boxed{123}$