Javascript Recursion -> what does the return trace look like?

Question

So, I'm just starting to explore recursion and am a little stuck on a concept. Here is a solution I located for a sum digits function ( f(126) = 1 + 2 + 6 = 9 ):

function sumDigits(num, sum){
if (num === 0) {
    return sum;
} else {
    sum += num % 10;
    num = Math.floor(num / 10);
    return sumDigits(num, sum);
}}

I traced it down to the base, so far everything makes sense:

**Trace**
f(126, 0)
    {
    sum = 6
    num = 12
    f(12, 6)
    }
f(12, 6)
    {
    sum = 8
    num = 1
    f(1, 8)
    }
f(1, 8)
    {
    sum = 9
    num = 0
    f(0, 9)
    }
f(0, 9) = 9

I guess what doesn't make sense to me is HOW the base case is being passed back through during unwinding? How exactly is it traveling?

I'm expecting a facepalm, but until I understand I don't think I could replicate this solution.

Thanks for your help!

What base? Do you mean the sum?

p.s.w.g
– p.s.w.g

2014-01-14 17:24:01 +00:00
Commented Jan 14, 2014 at 17:24 — p.s.w.g
– p.s.w.g, Commented Jan 14, 2014 at 17:24
you pass num and sum each time it fires.

dandavis
– dandavis

2014-01-14 17:24:13 +00:00
Commented Jan 14, 2014 at 17:24 — dandavis
– dandavis, Commented Jan 14, 2014 at 17:24
Sorry, by 'base' I meant 'base case' (edited) :)

i_made_that
– i_made_that

2014-01-14 17:58:24 +00:00
Commented Jan 14, 2014 at 17:58 — i_made_that
– i_made_that, Commented Jan 14, 2014 at 17:58

Wayne · Accepted Answer · 2014-01-14 17:45:10Z

5

The sum is accumulated and passed forward in each call to sumDigits. It's this value that's returned whenever the first argument equals 0. I find that it helps to write out the recursion explicitly:

sumDigits(123, 0);
    return sumDigits(12, 3);
        return sumDigits(1, 5)
            return sumDigits(0, 6) // the base case (sum = 6)
                return sum;

The final call returns 6. The previous call returns the result of the final call. The call before that returns the call before the final call (and so on). So they all end up unraveling the final sum.

Note that each call returns the result of the next call in the chain. What stops this is the base case (i.e. a condition that results in the return of a concrete value (i.e. no additional calls)).

edited Jan 14, 2014 at 17:45

answered Jan 14, 2014 at 17:36

Wayne

60.5k15 gold badges135 silver badges129 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

i_made_that Over a year ago

"It's this value that's returned whenever the first argument equals 0" -> Herein lies my confusion. What exactly gets passed back to say sumDigits(1,5) from sumDigits(0,6) on the return trip? The base case, right? But how does it travel? Ugh, so confused.

Wayne Over a year ago

If a returns b and b returns c and c returns 6, then b returns 6 and a returns 6.

IceArdor · Accepted Answer · 2014-01-14 21:02:28Z

0

I'd suggest

function sumDigits(num) {
    if (num < 0)
        return sumDigits(Math.abs(num)) //handle negative numbers
    least_sig_digit = num % 10
    if (num < 10)
        return least_sig_digit //in case num is a float)
    else
        return least_sig_digit + sumDigits(Math.floor(num / 10))
}

This way you will drill down until sumDigits returns the base case, and then bubble the result. By the time you reach the top of the call stack, you should have the sum of all digits.

Here's how this works:

sumDigits(126)
= 6 + sumDigits(12)
= (6+2) + sumDigits(1)
= (6+2+1)
= 9

The function calls are made from top-to-bottom order. The return value bubbles up in bottom-to-top order, eventually returning the value 9 for the expression sumDigits(126).

The best way to think about recursion is defining the behavior to move from one layer to the next, and not worry about the big picture. As long as you're satisfied when someone tells you 5! = 5*4!, it's a lot easier to conceptualize recursion.

What is sumDigits(126)? It's 6 + sumDigits(12). But what is sumDigits(12)? It's (6+2) + sumDigits(1). etc.

edited Jan 14, 2014 at 21:02

answered Jan 14, 2014 at 17:31

IceArdor

2,05122 silver badges20 bronze badges

2 Comments

i_made_that Over a year ago

Yes, this solution (aka, without the extra sum argument) is easier for me to make sense of. Although, recurring sumDigits calls should take the Math.floor(num / 10) argument rather than (num % 10), right?

IceArdor Over a year ago

That's correct. I originally wrote this function to sum the digits from most significant digit to least significant and forgot to update the code. The digits can be added either way (RTL or LTR).

slebetman · Accepted Answer · 2014-01-14 21:15:11Z

0

It's returning sum += num % 10 recursively.

Another way to think about it, it's returning sum but each call modifies sum (the += operator) such that when it gets to the base case the value of sum in the innermost loop is the actual sum. So just return that value through all the returns.

If you just want to print you don't even need to return anything. Just have the base case print the value of sum and return null.

The summing is done on the way in to the base case, not on the way out.

answered Jan 14, 2014 at 21:15

slebetman

115k19 gold badges148 silver badges180 bronze badges

2 Comments

slebetman Over a year ago

Note that in contrast the solution offered by IceArdor does the summing on the way out from the base case.

i_made_that Over a year ago

Right. So in my original solution, no 'work' is happening on the way out besides the passing back of sum?

Collectives™ on Stack Overflow

Javascript Recursion -> what does the return trace look like?

3 Answers 3

2 Comments

2 Comments

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

2 Comments

2 Comments

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related