This trace uses the technique demonstrated in tracing recursive methods and some of the material from the more complex stack based trace with nested recursive calls. Familiarity with the material from those resources is assumed, including the notation.

The same trace is available with each step on its own page, starting with Step 1.

Step 1: initial call

Initial call stack

r(32)

Step 2: recur(32)

• Computes 32 % 3, which is 2
• Computes "" + 2, which is "2"
• Creates dig and sets it to point to "2"
• Checks if 32 / 3, which is 10 is > 0, which is true
• Computes "2" + ___ (something unknown)
• Calls recur with 32 / 3, which is 10

Resulting call stack

r(10)
r(32)    dig -> "2"    "2" + ____

Step 3: recur(10)

• Computes 10 % 3, which is 1
• Computes "" + 1, which is "1"
• Creates dig and sets it to point to "1"
• Checks if 10 / 3, which is 3 is > 0, which is true
• Computes "1" + ____
• Calls recur with 10 / 3, which is 3

Resulting call stack

r(3)
r(10)    dig -> "1"    "1" + ____
r(32)    dig -> "2"    "2" + ____

Step 4: recur(3)

• Computes 3 % 3, which is 0
• Computes "" + 0, which is "0"
• Creates dig and sets it to point to "0"
• Checks if 3 / 3, which is 1 is > 0, which is true
• Computes "0" + ____
• Calls recur with 3 / 3, which is 1

Resulting call stack

r(1)
r(3)     dig -> "0"    "0" + ____
r(10)    dig -> "1"    "1" + ____
r(32)    dig -> "2"    "2" + ____

Step 5: recur(1)

• Computes 1 % 3, which is 1
• Computes "" + 1, which is "1"
• Creates dig and sets it to point to "1"
• Checks if 1 / 3, which is 0, is > 0, which is false
• Stops and returns "1"

Resulting call stack

r(1)  returns "1"
r(3)     dig -> "0"    "0" + ____
r(10)    dig -> "1"    "1" + ____
r(32)    dig -> "2"    "2" + ____

Step 6: Back in recur(3)

• Back in recur(3)
• Finished the recurusive call, got back "1"
• Computes "0" + "1", which is "01"
• Stops and returns "01"

Resulting call stack

r(1)  returns "1"
r(3)     dig -> "0"    "0" + "1"  returns "01"
r(10)    dig -> "1"    "1" + ____
r(32)    dig -> "2"    "2" + ____

Step 7: Back in recur(10)

• Back in recur(10)
• Finished the recursive call, got back "01"
• Computes "1" + "01", which is "101"
• Stops and returns "101"

Resulting call stack

r(1)  returns "1"
r(3)     dig -> "0"    "0" + "1"   returns "01"
r(10)    dig -> "1"    "1" + "01"  returns "101
r(32)    dig -> "2"    "2" + ____

Step 8: Back in recur(32)

• Back in recur(32)
• Finished the recursive call, got back "101"
• Computes "2" + "101", which is "2101"
• Stops and returns "2101"

Resulting call stack

r(1)  returns "1"
r(3)     dig -> "0"    "0" + "1"   returns "01"
r(10)    dig -> "1"    "1" + "01"  returns "101
r(32)    dig -> "2"    "2" + "101" returns "2101"