Hi.
This supposed to be a trivial thing, but people who didn’t went to computer science study, who were converted from computer engineer or machine’s engineer probably need some strengthening.
So why did i remember this ? because of job interviews 
not that it appears a lot but it helps understand the issues with recursions.
So I’ll start by explaining the big issue with recursion. I don’t like recursions, they are not so readable and are usually the most simple solution to a problem while there might be a simple iterative solution. Sometimes however the iterative solution is the bad one and the only probable solution is recursion. Not that you can’t do an iterative solution (8 queens sort for example) it will just look like recursion in the end, we’ll soon see how
when you use a recursion function, for example for calculation n! it might look something like this:
1 2 3 4 5 6 7 | int factorial(int n) { int res = 1; if (n != 1) { res = n * factorial(n - 1); } return res; } |
so where is the problem ? simple short code that gets you factorial number. well first of all this is a really simple code, so it’s just as easily could be translated to iterative code, later on I’ll show an example that’s not so easily done. The recursion in each iteration calls the function again, that’s the real power of recursion, the whole function state is saved and when you come back, you got everything waiting for you just the way it was! but how is the state saved ? where do al lthe variables are kept ? well folks, they are kept on the sack, since they are usually local variables they are kept on the stack… and it doesn’t matter if it’s java or C\C++ they are kept on the same place.
Ok so they are on the stack, what’s wrong with that ?? ah 
well basically it’s ok, that’s the way it works, but in big recursion functions that deals with large objects (that are defined locally, not as references, or create new objects) then you are consuming the stack with every function call, it can lead to stuck overflow…
There are couple of ways to make sure your function if memory effective and I’ll touch them after I’ll touch the main issue, how do i remove the data from the stack preventing stack overflow ? The answer is, you do not use recursion, but you need the saved data, you can’t do without it! so if you don’t use the OS stack, you can always use your own stack, STL or java Stack<> can certainly do the trick. all you need to do is thing of the stages that may come up inside a function call and turn them into states then you just do a while or for look that starts in the beginning and end when the stopping rule is achieved and then you can use switch – case to change betwee nthe different states and go over your data structure. Since it sounds a bit too theoretical let’s take it into practice:
Example #1, the factorial function:
The factorial is a really simple function, it looks as if it doesn’t reallyt have any state! the stop condition is if the function is called with 1, if not we return an arthimetic value. we can rewrite te function to understand the states:
1 2 3 4 5 6 7 8 9 10 | int factorial(int n) { int res = 1; if (n == 1) { res = 1; } else { res = factorial(n - 1); res *= n; } return res; } |
I think this form puts better emphasis on the states, we have an entry state, like we just entered the function with the n as our number and we have a returned sate which is like we just came back to the position where we left off our function by caling factorial(n1-). the resault will look something like this:
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 45 46 47 48 49 50 51 52 53 54 | public static int factorial(int n){ Stack stack = new Stack(); StateOject so = null; e_states state = e_states.in; int num = n; int res = 0; boolean stop = false; while( ! stop ){ switch(state){ case in: if(num==1){ res = 1; state = e_states.ret; } else{ so = new StateOject(num--, e_states.ret); stack.push(so); } break; case ret: so = stack.pop(); num = so.getNum(); res *= num; state = so.getState(); if( stack.isEmpty() ){ stop = true; } break; } } return res; } private enum e_states{ in, ret } private static class StateOject{ private int mNum; private e_states mState; public StateOject(int num, e_states state) { this.mNum = num; this.mState = state; } public int getNum() { return mNum; } public e_states getState() { return mState; } } |
so as you can see i’ve defined enum of two states, in and ret, i start off by putting the function in the in state and going into the while loop that will stop when we get to the end (meaning the stack is once again empty).
In the while loop we have switch case to have the two states, in the in state we check for ’1′ value in num, if it’s one it means that we have reached the stop ondition and change the state to ‘ret’, note that no one ever changes it back to ‘in’ if we wanted extra recursions we’ll have to save soem more data on the stack and change thestate back to in. In any way if the stop condition is not met we just create new stack object with the new state and the current ‘n’ and push it, then we just go on the while loop, mimicing a recursive function call. Once the state is changed to ret we check out the state and n and multiply the ‘n’ with the ‘res’ variable which mimic the returned value – like we can write ‘return 1′ or ‘return n*factorial(n-1)’ in the recursion we can write res = 1 and res = num*res, meaning res will contain the current returned valuein each loop.
So for this simple example it looks like a big overhead, you are right, when we can just simplify everything with a simple for loop that multiply n by it’s n-1 and decreasing n it’s really idiotic to write this way, but what if we can’t have a simple solution ?
Lets take a look on a different problem: mirroring binary tree
Let B be a Binary tree with R are it’s root. Let N be a generic node in the tree that is constructed like so:
- data
- left
- right
There is no known assumption on B, meaning it can be any kind of binary tree (balanced, non balanced, single list etc…)
Bm is the mirror of B if for each Node Ni in B node Nmi in Bm is:
- Nmi.data = Ni.data
- Nmi.left = Ni.right
- Nmi.right = Ni.left
So we want to write a function that will get as parameter R and will return Rm (root for mirrored tree).
The eaiset way to do it the recursion:
1 2 3 4 5 6 7 8 9 | public static Node mirrored(Node tree){ if(tree != null){ Node newLeft = mirrored(tree.right); Node newRight = mirrored(tree.left); tree.left = newLeft; tree.right = newRight; } return tree; } |
pretty simple right ? only one problem, what happens when you’ll have a tree with 1,000,000 nodes ? what will happen if all those nodes will be only on the tree’s right branch ? then we’ll have a linked list with 1M nodes that will reside in memory AND 1M iterations that will reside on the stack, not much space is left then for any other programs, includig kernel memory, and you are left with stack overflow… so we can prevent the stack overflow… but not the memory consumtion if we untangle this recursion we’ll just have the same 1M stackObjects on the stack, but at least it’s for us to control, you can always pay preformance penalty by writing part of the tree to disk working with 5000 nodes batches…
In any case here converting the recursion into iterative function is not so trival, how will you know who was your parent, how will you know if you turned left or right ? here you can’t get that easy without a stack.
here is the solution:
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 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 | public static Node mirroredNoRec(Node tree){ boolean stop = false; e_states state = e_states.goLeft; Stack stack = new Stack(); StateObject temp = null; Node currentNode = tree; while( ! stop ){ switch(state){ case goLeft: if( currentNode != null ){ swapSides(currentNode); temp = new StateObject(currentNode, e_states.goRight); stack.push(temp); currentNode = currentNode.right; }else{ state = e_states.ret; } break; case goRight: if( currentNode != null ){ temp = new StateObject(currentNode, e_states.ret); stack.push(temp); currentNode = currentNode.left; }else{ state = e_states.ret; } break; case ret: if( ! stack.isEmpty() ){ temp = stack.pop(); currentNode = temp.getRoot(); state = temp.getState(); } break; } } return tree; } private static void swapSides(Node n){ Node temp; temp = n.left; n.left = n.right; n.right = temp; } private static class Node{ private int data; private Node left; private Node right; public Node(int data, Node left, Node right){ this.data = data; this.left = left; this.right = right; } public int getData() { return data; } public Node getLeft() { return left; } public Node getRight() { return right; } } private enum e_states{ goLeft, goRight, ret } private static class StateObject{ private Node mroot; private e_states mState; public StateObject(Node root, e_states state) { this.mroot = root; this.mState = state; } public Node getRoot() { return mroot; } public e_states getState() { return mState; } } |
So true, it’s more complicated, but you control the stack rather then the OS…
There is antoerh solution, but i’ll discuss that one in my Next article regarding the other way to go through a binary tree.
I hope this was educational and if not, you got two more question ou know for job interviews.
Oh a small note before i go, if you want a simple software solution to the mirroring problem do the following:
- Left and right in the Node object are private and not an inner class so no one can access left and right but Node class itself
- make sure you got proper getter and setter
- add a wraper class if you can’t access the Node itself or add a local boolean variable mMirror.
- change the getters or the wrapper getter to return change the pointers it returns if the mMirror is true, meaning that the left getter will return the right pointer and the right getter the left pointer.
Enjoy
I really like examining and I conceive this website got some genuinely utilitarian stuff on it! .