0

I am not able to understand this basic recursion example.enter image description here

When I executed this code. The output was 43210. Should not the output be 44444, as the value of num is updated to 4 to the latest recursive call or how is the value of num getting changed?

Please explain, any help is appreciated.

  • Read more about recursion and run your program step by step in some debugger. Draw the call stack on some board. – Basile Starynkevitch Jun 16 '17 at 10:10
  • 3
    "as the value of num is updated to 4 to the latest recursive call or how is the value of num getting changed": num is not a global variable that gets updated at each call. Rather, num is local to each function call / activation. In other words, there is one copy of num for each active call to recursiveFunction. Each copy is defined locally in one function activation and does not influence the value of other copies, living in other activation records of recursiveFunction. – Giorgio Jun 16 '17 at 10:13
  • "To understand recursion, you must first understand recursion..." – Delioth Jun 16 '17 at 19:20
7

The hard-to-understand part of this kind of recursion is that there are many different variables involved, all of which are called "num".

Every time you call a function, a new copy of all the local variables in that function is created ("allocated"). (The formal name for the area in which this happens is "stack frame".)

The definition of local variables includes parameters, and the mechanism works even when the calling function and the called function are the same function definition. Combined, these two mechanisms results in a cascade of variables with different values existing at the same time (but only one in the currently active invocation).

A good tool for understanding this is a debugger with a stack frame viewer which allows you to expand the local variables in all currently existing frames, not just the topmost one. This allows you to check that yes, there is in fact a num with value 1 and a different num with value 2 at the same time.

  • "Every time you call a function, a new copy of all the local variables in that function is created ("allocated"). (The formal name for the area in which this happens is "stack frame".)" This explains it, so recursive functions are not memory efficient ? thanks :-) – penta Jun 16 '17 at 10:19
  • 6
    @penta You're right, recursion can lead to stack overflow if it goes on too deep. The first site in this network wasn't called "stackoverflow.com" for nothing! – Kilian Foth Jun 16 '17 at 10:27
  • @penta, also, recursion includes not just when a function calls itself (direct recursion), but also in an indirect form when some function, a, calls function b, which calls function a. – Erik Eidt Jun 16 '17 at 14:29
  • @penta, Also see tail call, which is a special case of recursion that is memory space efficient, and also is an optimization provided by some languages and/or their runtime. – Erik Eidt Jun 16 '17 at 14:30
  • @ErikEidt To clarify, a tail call is not inherently memory efficient, it just happens to be trivial for a compiler or interpreter to optimize. Without that optimization (and there are many language implementations that don't do it), it's just as memory space costly as the general case recursive call. – 8bittree Jun 16 '17 at 15:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.