Passing a slice to recursive function in Python

Question

I think I understand the basic principles of recursive functions and slicing (individually), but I am having trouble putting them together. I don't understand what happens when you pass a slice or a list to the following function.

def listSum(ls):
    # Base condition
    if not ls:
        return 0

    # First element + result of calling `listsum` with rest of the elements
    return ls[0] + listSum(ls[1:])

listSum([1, 3, 4, 5, 6])
19

This is the thread that contains this code: Understanding recursion in Python

I think I would really benefit from a walk-through of what happens when the function is called.

The thread has a lot of examples of different recursive functions, with the expected output. I understand the subsequent examples even less than the one I copied above.

A slice simply creates a new list. You don't really pass a *slice*, you take a slice of a list to create a new list, then pass that — juanpa.arrivillaga, Jan 16 '18 at 19:44
If you need a walk through try running your code through http://www.pythontutor.com/visualize.html#mode=edit and clicking 'Visual Execution' — TheoretiCAL, Jan 16 '18 at 19:46
it adds 1 plus the rest of the list without 1, so `1 + (2 +( 3+ (4+ (5+ (6 + 0)))))` — Patrick Artner, Jan 16 '18 at 19:47
The sum of a list is the first thing in the list (`ls[0]`) plus the sum of the rest (`listSum(ls[1:]`). — internet_user, Jan 16 '18 at 19:49
splice returns a new list. The function listSum takes a list. It's a match! The recursion is simple "sum = first + sum(rest)". — Kenny Ostrom, Jan 16 '18 at 19:49
Turns out I didn't actually understand slicing. Thank you all for the replies! — jeffrlynn, Jan 16 '18 at 20:13
Note that creating a new list for each recursive call is *very* inefficient. — jpmc26, Jan 16 '18 at 22:32

score 1 · Accepted Answer · answered Jan 16 '18 at 19:50

The basic concept of recursion is that each call consumes part of the input, reducing it until it matches the base case.

Here, the base case is is if not ls, which will be true when ls is an empty list.

The consumption is done via slicing: each call passes a list that is one element shorter than the last one. This is accomplished with listSum(ls1:]), which calls listSum on a list composed of all elements of ls except the first.

That first element is then added to the result of the recursive call and returned. Since there will be one recursive call for element of ls, each number in ls gets at turn to be the one popped off and summed, that is, consumed.

Going through it step by step, we're going to add

1 + listSum( [3, 4, 5, 6] )

which is

1 + 3 + listSum( [4, 5, 6])

which is

1 + 3 + 4 + listSum( [5, 6] )

which is

1 + 3 + 4 + 5 + listSum( [6] )

which is

1 + 3 + 4 + 5 + 6 + listSum([])

which, because of the base case, is

1 + 3 + 4 + 5 + 6 + 0

which is 19.

Mulan · Answer 2 · 2018-01-16T21:16:51.447

List traversal baby steps

For traversing lists using recursion, there's only 3 things that matter

the empty list - always check if your list is empty before anything!
the head of the list – the first item
the tail of the list – the entire list except the first item

Ok, and here's the functions we'll use to write our programs

def is_empty (ls):
  return ls == []

def head (ls):
  return ls[0]

def tail (ls):
  return ls[1:]

Usage of the functions is straightforward

is_empty ([])           # => True
is_empty ([ 1, 2, 3 ])  # => False

head ([ 1, 2, 3 ])      # => 1

tail ([ 1, 2, 3 ])      # => [2,3]

Ok, so let's write our list_sum function – I think you'll agree that we ended up with a very readable program thanks to the list helpers we defined

def list_sum (ls):
  if is_empty (ls):
    return 0
  else:
    return head (ls) + list_sum (tail (ls))

print (list_sum ([ 1, 2, 3, 4, 5, 6, 7 ]))
# => 28

But you tagged this with tail recursion, so with the help of an optional parameter and a default value, we can move the recursive call into tail position. Changes in bold

def list_sum (ls, acc = 0):
  if is_empty (ls):
    return acc
  else:
    return list_sum (tail (ls), head (ls) + acc)

print (list_sum ([ 1, 2, 3, 4, 5, 6, 7 ]))
# => 28

But Python doesn't really have tail-call elimination, so you'd still have to do something else to ensure stack-safety.

Smoke higher-order functions every day

Using head and tail relieved us from the tedium (and ugliness) of [0] and [1:], but this pattern of list traversal is so common that we can relieve ourselves from even thinking at this level altogether!

Let's look back at our function, list_sum. This function traverses a list and performs addition using the built-in + function. What if instead of + we wanted to multiply all the elements using *?

def list_sum (ls):
  if is_empty (ls):
    return 0
  else:
    return head (ls) + list_sum (tail (ls))

def list_product (ls):
  if is_empty (ls):
    return 1
  else:              
    return head (ls) * list_product (tail (ls))

print (list_product ([ 1, 2, 3, 4, 5, 6, 7 ]))
# => 5040

The only thing that's different is 0 changed to 1 and + changed to *. We don't want to rewrite all of that each time we want to do something with a list. If we abstract those values using function parameters, we can capture the very essence of list traversal in this nice little program

from operator import add, mul

def list_reduce (f, acc, ls):
  if is_empty (ls):
    return acc
  else:
    return list_reduce (f, f (acc, head (ls)), tail (ls))

def list_sum (ls):
  return list_reduce (add, 0, ls)

def list_product (ls):
  return list_reduce (mul, 1, ls)

print (list_sum ([ 1, 2, 3, 4, 5, 6, 7 ]))
# => 28

print (list_product ([ 1, 2, 3, 4, 5, 6, 7 ]))
# => 5040

And higher-order functions can be built using other higher-order functions. Then before you know it, you're doing all sorts of high-level transformations and traversals!

Notice how we're not thinking about head or tail at this point. Hard-on-brain things like not [], ls[0] and ls[1:] are out-of-sight and consequently out-of-mind.

def map (f, ls):
  return list_reduce (lambda acc, x: acc + [ f (x) ], [], ls)

def square (x):
  return x * x

print (map (square, [ 1, 2, 3, 4, 5, 6, 7 ]))
# => [1, 4, 9, 16, 25, 36, 49]

Passing a slice to recursive function in Python

2 Answers2