permaculture playing cards*
The moose likes Performance and the fly likes Question about mem allocation for recursive functions Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login


Win a copy of Android Security Essentials Live Lessons this week in the Android forum!
JavaRanch » Java Forums » Java » Performance
Bookmark "Question about mem allocation for recursive functions" Watch "Question about mem allocation for recursive functions" New topic
Author

Question about mem allocation for recursive functions

Igor Oakgrove
Greenhorn

Joined: Jan 08, 2011
Posts: 5

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

Joined: Sep 20, 2010
Posts: 3605
    
  14

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

Joined: Jul 08, 2003
Posts: 24183
    
  34

The second one is worse, as its stack frames are 3 times as large!


[Jess in Action][AskingGoodQuestions]
 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: Question about mem allocation for recursive functions
 
Similar Threads
using this recursive method slows me down....why?
Recursion
Recursion of Fibonacci Numbers
Recursion Reciprocals
Timing Methods