Question

Is that true that any iterative routine can be implemented in a recursive way? I was wondering if it is possible to implement the last problem in ps4 recursively. It looks pretty challenging.

Answer 1

In theory, you might be able to implement any iterative routine recursively, but in practice it would be more trouble than it's worth, and if the number of iterations is large enough, you'll start to run into language/OS limits on recursion depth.

As far as doing ps4 recursively, recursion is mostly used for traversal or problems that can be completely solved by combining the results of solutions to part of the problem.

Answer 2

I got that done using an iterative approach and decided to translate the script into a recursive fashion as an exercise, using the same header provided in the ps4.py file. I'm not sure, but it looks like impossible to do that without passing the variable 'expenses' as a parameter in the function findMaxExpenses. 'expenses' is the only variable whose value is modified by the routine. Since I'm not passing this value as a parameter, my function kind of has no memory, it doesn't retain the previous value and so it cannot make successive approximations.

Answer 3

Adding the condition that the function retain it's signature changes things. The theoretical can it be done is different than can it be done with this prototype.

Looking over some old, poorly commented, code, it doesn't look possible without changing the prototype.

Answer 4

That's what I thought. Thank you very much for your attention Smith. I appreciated that.

Answer 5

But still, talking about balance betwin recursion and iteration. According to Church's thesis, any algorithm can be realised as some of partly recursive functions. It particulaly means, that in general case, in addition to recursion you may need iteration (of "while" kind).

Answer 6

its pretty easy to write a recursive procedure for an iterative process
http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-11.html#%_sec_1.2.1