4 ms·

Can't recursion do multithreading whereas iteration cannot?

• Jtsummers 11y ago
  It doesn't particularly matter. The loop: a, b = some input arrays of identical length c = the output array for(int i = 0; i < c.length; i++) c[i] = a[i]+b[i] can be easily run in parallel, each iteration of the loop kernel is independent of every other iteration. And, with OpenMP a #pragma could make that loop run in parallel without any difficulty (long time since I've used it, forgotten the actual code needed to make it happen but it's easy). vector_sum([],[]) -> []; vector_sum([A|Atail],[B|Btail]) -> [A+B|vector_sum(Atail,Btail)] (it's been a while since I erlanged, probably messed up the syntax) Each iteration should be independent, but the way we've constructed it it's not easily transformed to run in parallel now. In fact, that's a bad construction because erlang does have TCE and that recursion isn't in tail-call form. EDIT: Also, iteration and recursion are transformable to each other. If you have a language with tail-call elimination, then recursive code with tail-calls should be equivalent to code using more conventional loop structures. If no data needs to be retained between the recursive calls (consider this probably bad code): int[] vector_add(int[] A,B,C, int index) { if(index == C.length) return C; C[index] = A[index]+B[index]; return vector_add(A,B,C,index++); } assuming A,B, and C are all initialized correctly outside this call, it's fundamentally identical to (with TCE, actual assembly may not be the same without a bit more care taken in defining the function): int[] vector_add(int[] A,B,C) { for(int i = 0; i < C.length; i++) C[i] = A[i] + B[i]; return C; } That's a trivial transformation. Now, if we need to somehow retain some data (like an accumulator) it's not much harder: int factorial(int N) { int result = 1; for(int i = 1; i <= N; i++) result *= i; return result; } int factorial(int N, int result) { if(N = 0) return result; return factorial(N-1, result*N); } call the second one as factorial(N, 1), you'd likely have a wrapper to abstract that out for any user so they only have to call factorial(N). What if the recursion isn't a tail-call, how can we transform it? (bad factorial): int bad_factorial(N) { if (N == 0) return 1; return N * bad_factorial(N-1); } Assuming we want to keep this stack, the equivalent code with a loop would be like: int bad_factorial(N) { int result = 1; Stack values = new Stack(); for(; N > 0; N--) values.push(N); while(!values.isEmpty()) result = values.pop(); return result; } That stack we've created replaces the program stack that was used implicitly in the recursive version. I won't guarantee the performance or assembly is identical (they won't be) but they're on the same order for both execution time and memory use.
  • Zikes 11y ago
    Ahh, that makes sense. Thanks!