Analyzing a recursive algorithm

Question

I'm trying to figure out this algorithm that accepts an input of an int and should return an output of the sum of each element in the int.

# Input -> 4321
# output -> 10 (4+3+2+1) 

def sum_func(n):

    # Base case
    if len(str(n)) == 1:
        return n

    # Recursion
    else:
        return n%10 + sum_func(n/10)

When Trying to break apart this algorithm this is what I come up with

1st loop -> 1 + 432 = 433
2nd loop -> 2 + 43 = 45
3rd loop -> 3 + 4 = 7
4th loop -> 4 + 4 = 8

How was it able to come up with the result of 10?

1) there is no loop in the code; 2) the first expression should be 1 + sum_func(432) where the second term gives a result of 9 if you dig into it. — Henry
– Henry, Commented May 10, 2018 at 17:18
(for all positive n) len(str(n)) == 1 is an odd way of writing n < 10 — Mulan
– Mulan, Commented May 10, 2018 at 17:51
Looks like you're using Python. Be sure to compare n/10 vs n//10 — Mulan
– Mulan, Commented May 10, 2018 at 17:53

danh · Accepted Answer · 2018-05-10 17:18:45Z

5

Unwinding, it would look like this:

sum_func(4321)
= 1 + sum_func(432)
= 1 + 2 + sum_func(43)
= 1 + 2 + 3 + sum_func(4)
= 1 + 2 + 3 + 4

answered May 10, 2018 at 17:18

danh

62.7k10 gold badges100 silver badges139 bronze badges

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

Comments

Aivean · Accepted Answer · 2018-05-10 17:21:15Z

3

When trying to understand recursion you'll have to clearly understand what is returned.

In this case function sum_func(n) returns the sum of the digits in it's argument n.

For concrete n task is divided into last_digit_of_n + sum_func(n_without_last_digit).

For example,

sum_func(4321) = sum_func(432) + 1 = sum_func(43) + 2 + 1 = sum_func(4) + 3 + 2 + 1 = 4 + 3 + 2 + 1

Hope this helps.

(As a side note, checking if n has more than one digit using str is a bad idea. Better just to check if n <= 9)

answered May 10, 2018 at 17:21

Aivean

10.9k28 silver badges40 bronze badges

1 Comment

edmamerto Over a year ago

This drove me crazy and you explained it in a very simple way thanks!

Sarah · Accepted Answer · 2018-05-10 17:41:40Z

0

You must reach the base case before the summation occurs:

Iteration 1: 1 + sum_func(432)
Iteration 2: 1 + 2 + sum_func(43)
Iteration 3: 1 + 2 + 3 + sum_func(4) = 1 + 2 + 3 + 4 = 10

answered May 10, 2018 at 17:41

Sarah

811 silver badge4 bronze badges

Collectives™ on Stack Overflow

Analyzing a recursive algorithm

3 Answers 3

Comments

1 Comment

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Related