Understanding how recursive functions work

by

1.The function is called recursively until a condition is met. That condition is a > b. When this condition is met, return 0. At first glance, I would expect the return value to be 0 which is obviously incorrect.

Here is what the computer computing sumInts(2,5) would think if it were able to:

I want to compute sumInts(2, 5)
for this, I need to compute sumInts(3, 5)
and add 2 to the result.
  I want to compute sumInts(3, 5)
  for this, I need to compute sumInts(4, 5)
  and add 3 to the result.
    I want to compute sumInts(4, 5)
    for this, I need to compute sumInts(5, 5)
    and add 4 to the result.
      I want to compute sumInts(5, 5)
      for this, I need to compute sumInts(6, 5)
      and add 5 to the result.
        I want to compute sumInts(6, 5)
        since 6 > 5, this is zero.
      The computation yielded 0, therefore I shall return 5 = 5 + 0.
    The computation yielded 5, therefore I shall return 9 = 4 + 5.
  The computation yielded 9, therefore I shall return 12 = 3 + 9.
The computation yielded 12, therefore I shall return 14 = 2 + 12.

As you see, some call to the function sumInts actually returns 0 however this not the final value because the computer still has to add 5 to that 0, then 4 to the result, then 3, then 2, as described by the four last sentences of the thoughts of our computer. Note that in the recursion, the computer does not only have to compute the recursive call, it also has to remember what to do with the value returned by the recursive call. There is a special area of computer’s memory called the stack where this kind of information is saved, this space is limited and functions that are too recursive can exhaust the stack: this is the stack overflow giving its name to our most loved website.

Your statement seems to make the implicit assumption that the computer forgets what it were at when doing a recursive call, but it does not, this is why your conclusion does not match your observation.

2.Printing out the value of ‘a’ on each iteration yields a value which I would expect: 2, 3, 4, 5 (at which point 5+1 > b which meets the first condition: a > b) but I still don’t see how the value of 14 is achieved.

This is because the return value is not an a itself but the sum of the value of a and the value returned by the recursive call.

More Related Contents:

  1. How to explain callbacks in plain english? How are they different from calling one function from another function?
  2. “Parameter” vs “Argument” [duplicate]
  3. Define a recursive function within a function in Go
  4. What is tail recursion?
  5. Table name as a PostgreSQL function parameter
  6. What in layman’s terms is a Recursive Function using PHP
  7. Recursive function to generate multidimensional array from database result
  8. Recursion or Iteration?
  9. Define table and column names as arguments in a plpgsql function?
  10. What is the difference between a “function” and a “procedure”?
  11. Is there a way to use two ‘…’ statements in a function in R?
  12. What decides if a value is returned from a PowerShell function?
  13. Committing transactions while executing a postgreql Function
  14. Stack overflow caused by recursive function
  15. How to alias a function name in Fortran
  16. Static vs class functions/variables in Swift classes?
  17. How to profile methods in Scala?
  18. Whats the difference of functions and methods in Go?
  19. Return a list from the function using OUT parameter
  20. “Identifier Expected” or “Invalid Prototype” when implementing a scripted constant in Inno Setup
  21. Exporting a function in shell
  22. D3 Key Function
  23. Recursion or iteration?
  24. Kotlin: How can I create a “static” inheritable function?
  25. Haskell operator vs function precedence
  26. Scala Functional Literals with Implicits
  27. Does dart support operator overloading
  28. How many lines of code should a function/procedure/method have? [duplicate]
  29. Algorithm for iterating over an outward spiral on a discrete 2D grid from the origin
  30. Proper use of modules in Fortran

Leave a Comment