• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Jeanne Boyarsky
  • Ron McLeod
  • Paul Clapham
  • Liutauras Vilda
Sheriffs:
  • paul wheaton
  • Rob Spoor
  • Devaka Cooray
Saloon Keepers:
  • Stephan van Hulst
  • Tim Holloway
  • Carey Brown
  • Frits Walraven
  • Tim Moores
Bartenders:
  • Mikalai Zaikin

Question about mem allocation for recursive functions

 
Greenhorn
Posts: 5
VI Editor
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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
 
Saloon Keeper
Posts: 15484
363
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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.

 
author and iconoclast
Posts: 24207
46
Mac OS X Eclipse IDE Chrome
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
The second one is worse, as its stack frames are 3 times as large!
 
With a little knowledge, a cast iron skillet is non-stick and lasts a lifetime.
reply
    Bookmark Topic Watch Topic
  • New Topic