How to rewrite recursion in a more ruby way
It looks pretty good to me. Some notes: 


I'd avoid return on the last expression
I'd avoid the "-=" (not very functional)
I'd avoid inline returns (write a full-fledged conditional instead) 
I have my doubts about this more_friends.users &lt;&lt;, is this a side-effect you are doing behind the caller's back? 


As a general note, Ruby is an OOP language, you can strive for functional style (I do whenever possible), but still, use also an OOP structure or you'll end up with weird undiomatic code.