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.

Improve this question
3
  • Read more about recursion and run your program step by step in some debugger. Draw the call stack on some board. Commented Jun 16, 2017 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. Commented Jun 16, 2017 at 10:13
  • "To understand recursion, you must first understand recursion..." Commented Jun 16, 2017 at 19:20

1 Answer 1

Reset to default
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.

Improve this answer
6
  • "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 :-) Commented Jun 16, 2017 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! Commented Jun 16, 2017 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. Commented Jun 16, 2017 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. Commented Jun 16, 2017 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. Commented Jun 16, 2017 at 15:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.