question

Given a stack, find an element in the middle position of the stack. Optimize for space.

Recursion would be most efficient.

Using recursion, calculate how large the stack is on the way down and then return the appropriate element on the way back up.

Thoughts or alternate solution? Let us know in the comments below!

```
```

int getMiddle(stack* s, int pos, int* depth)

**if** (s.empty()) // reached bottom of stack

*depth = pos;

**return** 0;

int value = s.pop();

int result = getMiddle(s, pos + 1, depth)

s.push(value);

**if** (pos == *depth/2)

**return** value;

**return** result;

int depth;

getMiddle(&s, 0, &depth)

Thoughts or alternate solution? Let us know in the comments below!