CODEWITHSUNDEEP
javascriptrecursion
i_made_that
i_made_that

Reputation: 947

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

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!

Upvotes: 4

Views: 101

Answers (3)

slebetman
slebetman

Reputation: 113906

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.

Upvotes: 0

IceArdor
IceArdor

Reputation: 2041

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.

Upvotes: 0

Wayne
Wayne

Reputation: 60414

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)).

Upvotes: 5

Related Questions