File APIs for Java Developers
Manipulate DOC, XLS, PPT, PDF and many others from your application.
http://aspose.com/file-tools
Win a copy of Clojure in Action this week in the Clojure forum!
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic

Question about mem allocation for recursive functions

 
Igor Oakgrove
Greenhorn
Posts: 5
VI Editor
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hi, my first post here.
I've been trying to wrap my mind around memory allocation for recursive functions.
As far as my understanding goes a recursive function has to go all the way down in the recursion chain until a definite value is returned and consecutive results bubble up. Every recursion step towards that definite return value requires some memory allocation which can lead to stack overflow (like in the example below).



In a book, i came across an example which supposedly solves the stack overflow problem but i cant see how. Is memory still allocated in same fashion as in example above?



Regards
Igor
 
Stephan van Hulst
Bartender
Pie
Posts: 4840
34
Chrome Netbeans IDE Windows
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Welcome to JavaRanch, Igor.

I quickly looked at the algorithm, and it appears to do exactly the same thing as the first one, the only difference being that the first one calculates a factorial starting with n, and the second one starts with 1.

As a matter of fact, the second algorithm will fail for n == 0.

They both use O(n) stack frames.

 
Ernest Friedman-Hill
author and iconoclast
Marshal
Pie
Posts: 24204
34
Chrome Eclipse IDE Mac OS X
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
The second one is worse, as its stack frames are 3 times as large!
 
I agree. Here's the link: http://aspose.com/file-tools
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic