import sys sys.setrecursionlimit(1500)
Any recursive function can be made to iterate (into a loop) but you need to use a stack yourself to keep the state.
Normally, tail recursion is easy to convert into a loop:
A(x) {
if x<0 return 0;
return something(x) + A(x-1)
}
Can be translated into:
A(x) {
temp = 0;
for i in 0..x {
temp = temp + something(i);
}
return temp;
}
Other kinds of recursion that can be translated into tail recursion are also easy to change. The other require more work.
The following:
treeSum(tree) {
if tree=nil then 0
else tree.value + treeSum(tree.left) + treeSum(tree.right);
}
Is not that easy to translate. You can remove one piece of the recursion, but the other one is not possible without a structure to hold the state.
treeSum(tree) {
walk = tree;
temp = 0;
while walk != nil {
temp = temp + walk.value + treeSum(walk.right);
walk = walk.left;
}
}