1

I am trying to write a recursive function to sum up the digits in a number. This is how I did it:

def f(N):
    sum = 0
    return foo(N,sum)

def foo(N, sum):
    if N < 10:
        sum = sum + N
#        print 'N=', N
        return sum
    else:
        sum = sum + N%10
#        print 'N=', N, 'sum= ', sum
        return sum and foo(N/10,sum)


res =  f(5)
print 'N=5', 'res=', res
res =  f(59)
print 'N=59', 'res=', res
res =  f(568)
print 'N=568', 'res=', res

Is it possible to have a simpler recursion using only the f-function, i.e. no 'foo' function?

m.cekiera
  • 5,365
  • 5
  • 21
  • 35
CFR
  • 11
  • 2

3 Answers3

2

You do not need to pass the sum every time

def f(N):
    if N < 10:
        return N
    else:
        return N%10 + foo(N/10)

Add prints as you like. This will build out the expression and add them together after it reaches the bottom.

Note* this will break if N is negative. You can add a simple check in the beginning and perform a similar operation with negation.

Dan
  • 383
  • 1
  • 4
0

The form of recursion that you currently have, which passes the current sum through recursive calls, is a special form of recursion called tail recursion. Tail recursive calls typically use helper functions to get them started. Since there's no real operations done with the result of the recursive call, it can just return it immediately without allocating more stack space. Some compilers make this optimization for tail-recursive code, so I'd personally prefer your existing code.

You can of course re-write the function into a single recursive function by just returning the current result combined with the recursive call. 

def foo(N):
    if N < 10:
        return sum
    else:
        return sum%10 + foo(N/10)

The downside to this form of recursion is that you can potentially run out of stack space. In this case, each recursive call depends on the result of all the next calls, so the local memory for the original function call can get bloated while waiting for its recursion (and that call's recursions) to return.

Community
  • 1
  • 1
ryanyuyu
  • 6,366
  • 10
  • 48
  • 53
0

python really isn't a good language for recursion (while loops are better), but for educational purposes, you can do the following 

def foo(N, sum1=0):
    if N < 10:
        sum1 = sum1 + N
        return sum1
    else:
        sum = sum1 + N%10
        return foo(N/10,sum1)

foo(10) 
=> 1

notice the sum=0 in the method parameters, this is a default value of the parameter, and it will be "initialized" to it if no parameter passed. (note, the keywork 'sum' is a built in python method, and assignment to it should be avoided.)

For non-educational purposes, might I suggest using

foo = lambda n: sum(map(int,str(n)))

foo(10)
=>1

this converts the number into a string, changes the characters back into ints, then sums them. It skips all the pesky division.

pseudonym
  • 1