Featured post
c++ - Problem with Tail Recursion in g++ -
i'm messing around tail-recursive functions in c++, , i've run bit of snag g++ compiler.
the following code results in stack overflow when numbers[]
on couple hundred integers in size. examining assembly code generated g++ following reveals twosum_helper executing recursive call
instruction itself.
the question of following causing this?
- a mistake in following overlooking prevents tail-recursion.
- a mistake usage of g++.
- a flaw in detection of tail-recursive functions within g++ compiler.
i compiling g++ -o3 -wall -fno-stack-protector test.c
on windows vista x64 via mingw g++ 4.5.0.
struct result { int i; int j; bool found; }; struct result gen_result(int i, int j, bool found) { struct result r; r.i = i; r.j = j; r.found = found; return r; } // return 2 indexes numbers sum target. struct result twosum_helper(int numbers[], int size, int target, int i, int j) { if (numbers[i] + numbers[j] == target) return gen_result(i, j, true); if (i >= (size - 1)) return gen_result(i, j, false); if (j >= size) return twosum_helper(numbers, size, target, + 1, + 2); else return twosum_helper(numbers, size, target, i, j + 1); }
tail call optimization in c or c++ extremely limited, , pretty lost cause. reason there no safe way tail-call function passes pointer or reference local variable (as argument call in question, or in fact other call in same function) -- of course happening on place in c/c++ land, , impossible live without.
the problem seeing related: gcc compiles returning struct passing address of hidden variable allocated on caller's stack callee copies -- makes fall above scenario.
- Get link
- X
- Other Apps
Comments
Post a Comment