3

In a recursive function in C++, one of its argument is reference type. I just want to know what will happen during the recursive call of the function.

Without reference type, I believe every time the function is called recursively, a new variable will be created in the stack. So with the reference, every time what has been created in stack now is some kind of pointer pointing to the address of the original variable where it is declared,right?

So by using reference in such scenario, I believe sometimes we can save some memory.

Peter Mortensen
  • 30,738
  • 21
  • 105
  • 131
Hao Shen
  • 2,605
  • 3
  • 37
  • 68
  • IMHO - Avoid recursion in the first place - more trouble than it is worth – Ed Heal Feb 01 '14 at 04:35
  • Yes, internally a pointer is passed. References can be understood as pointers that can't be null. – epx Feb 01 '14 at 04:37
  • 1
    @Ed: There are [places where recursion is the best tool for the job](http://stackoverflow.com/a/9056893/103167), and avoiding it is more trouble. – Ben Voigt Feb 01 '14 at 04:56
  • @BenVoigt - Cannot think of any. Use a stack instead. Or tail recursion that is just a loop – Ed Heal Feb 01 '14 at 05:00
  • 4
    In what way is using a stack to simulate recursion less trouble than using recursion? – Brian Bi Feb 01 '14 at 05:11

2 Answers2

1

Yes, you've got the right idea. Note, of course, that you only save memory if the parameter type is larger than a pointer. A reference to an integer (or maybe even a double) won't save any memory on the stack.

Mike Woolf
  • 1,210
  • 7
  • 11
1

Usually parameter values change during recursion. You can't simply share those across all levels.

Furthermore, when a function is not inlined (and recursion interferes with inlining), passing an argument by reference costs as much space as a pointer.

Ben Voigt
  • 277,958
  • 43
  • 419
  • 720
  • Why not share them across levels? Consider a reference to an object collecting stuff as it goes. BTW How does an inline function and recursion correlate. Surely an inlined function cannot utilize recursion – Ed Heal Feb 01 '14 at 05:06
  • @Ed: An object "collecting stuff as it goes" is just an explicit stack instead of implicit on call stack. It doesn't fulfill the desire of the question to "save some memory". And I said that recursion interferes with inlining (it prevents inlining beyond a certain depth *unless it can be converted to iteration*) – Ben Voigt Feb 01 '14 at 07:18
  • It will - instead of aggregating the partial results. – Ed Heal Feb 01 '14 at 07:46
  • Aggregating doesn't mean what you think it does. And in my preferred style, I would pass an iterator to the end of the list, by value, and that iterator would be changing in every call, so not sharable. If you aren't changing the arguments in every recursion step I have to ask why you are using recursion in the first place. – Ben Voigt Feb 01 '14 at 07:50
  • Two parts to recursion. Passing arguments to do the recursion. Passing arguments to collect the results.Consider searching a binary tree to produce another tree (a subset). One parameter is the search idea. THe other being where to add any results to. – Ed Heal Feb 01 '14 at 07:56
  • 1
    @BenVoigt Yes. I also agree with Ed. Without reference, when we want to repeatedly add something to the "result" argument and finally print the result out, we will "aggregate the partial results". – Hao Shen Feb 01 '14 at 16:05
  • 1
    @Hao: I think Ed may have meant "accumulate", not "aggregate". Aggregation would take less memory than "collecting stuff" for later processing. – Ben Voigt Feb 01 '14 at 18:23