Win a copy of Kotlin in Action this week in the Kotlin forum!
  • Post Reply Bookmark Topic Watch Topic
  • New Topic

Printing a File in Reverse Order Using Recursion  RSS feed

 
Mohammed Azeem
Ranch Hand
Posts: 56
3
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Good Afternoon everyone,

I'm self-studying a series of lectures and I'm on the lecture about recursion.

Class PrintFileInForwardOrder prints a file from start to end in the normal order. I have tried it, I understand it and can trace through it:




Class PrintFileInReverseOrder should prints the file in reverse order, but it doesn't - it prints in the forward order.
It doesn't look very different from class PrintFileInForwardOrder.
* Am I missing something?
* Could someone trace through the recursive method for me, so I can appreciate what I am missing ?

Help on coderanch is always astonishing. And I am grateful.

 
Dave Tolls
Rancher
Posts: 2914
36
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
At the moment both those codes are doing the same thing:
call printRecursive which:
reads a line
prints that line
calls itself

And so on, which results in it printing in order, because it prints before calling itself (in other words it's printing on the way down).
You want it to print on the way back up the call chain.
 
Mohammed Azeem
Ranch Hand
Posts: 56
3
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Thanks Dave Tolls,

You're right but I had to sit down and know why and how you were right.

What I was forgetting is that each method has its own local variable which is stored in its stack frame on the stack - until the method returns. So, in recursive calls, there's a whole load of local variable of type String line each in its own stack frame corresponding to its own recursive method.

When finally the base case becomes true, the last recursion returns, setting off a whole cascade of returns.

I'm a visual learner so I've done the following diagram to help any others who like me who were bewildered - click on link: https://drive.google.com/open?id=0B8OWbv_QuY22Z3JBdk90UzAxM1E

As I said I was self-studying a series of lectures - no wonder then that the previous lecture spent a lot of time talking about static storage, stacks and heaps - it all fits in.


Thank you David for setting me off on understanding the nitty-gritty of this.


 
Henry Wong
author
Sheriff
Posts: 23283
125
C++ Chrome Eclipse IDE Firefox Browser Java jQuery Linux VI Editor Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Mohammed Azeem wrote:
I'm a visual learner so I've done the following diagram to help any others who like me who were bewildered - click on link: https://drive.google.com/open?id=0B8OWbv_QuY22Z3JBdk90UzAxM1E


Thanks for thinking of others, and following up with details ... you earned a cow.

Henry
 
Winston Gutkowski
Bartender
Posts: 10573
65
Eclipse IDE Hibernate Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Mohammed Azeem wrote:As I said I was self-studying a series of lectures - no wonder then that the previous lecture spent a lot of time talking about static storage, stacks and heaps - it all fits in.

Oddly enough, that's exactly what I was thinking, because nobody in their right mind would write a recursive method to read a file backwards; but when you understand how stacks work, it all makes sense (or hopefully it does).

Well done! And have a cow from me too.

Winston
 
salvin francis
Bartender
Posts: 1607
36
Eclipse IDE Google Web Toolkit Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Winston Gutkowski wrote: ...exactly what I was thinking, because nobody in their right mind would write a recursive method to read a file backwards; but when you understand how stacks work, it all makes sense (or hopefully it does)


I still am a bit doubtful about this ... Will it scale well for a huge file ? (I think there could be a stackoverflow lurking behind it, I may be wrong )
 
Winston Gutkowski
Bartender
Posts: 10573
65
Eclipse IDE Hibernate Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
salvin francis wrote:I still am a bit doubtful about this ... Will it scale well for a huge file ? (I think there could be a stackoverflow lurking behind it, I may be wrong )

Nope. And in general (and specifically in Java) recursion doesn't scale well - which is why it's usually only used for "divide and conquer" problems, or ones with a strict "depth" limit.

Winston
 
Mohammed Azeem
Ranch Hand
Posts: 56
3
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Thank you Henry and Winston for your cows.
 
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!