# Playing with Python - recursion

Page 1 of 1

## 7 Replies - 2305 Views - Last Post: 17 October 2012 - 03:05 PMRate Topic: //<![CDATA[ rating = new ipb.rating( 'topic_rate_', { url: 'http://www.dreamincode.net/forums/index.php?app=forums&module=ajax&section=topics&do=rateTopic&t=295970&amp;s=d639c62f2d203417b283286fa1a906a6&md5check=' + ipb.vars['secure_hash'], cur_rating: 0, rated: 0, allow_rate: 0, multi_rate: 1, show_rate_text: true } ); //]]>

### #1 darek9576

• D.I.C Lover

Reputation: 202
• Posts: 1,705
• Joined: 13-March 10

# Playing with Python - recursion

Posted 17 October 2012 - 05:09 AM

So, i implemented the function that checks whether 2 lists are equal and i was wondering whether it is somehow possible to use the recursion and exit the function witout IndexError or raising an error and catching it is the only option.
Thanks.

Spoiler

Is This A Good Question/Topic? 0

## Replies To: Playing with Python - recursion

### #2 SegFaulty

Reputation: 14
• Posts: 35
• Joined: 11-October 10

## Re: Playing with Python - recursion

Posted 17 October 2012 - 08:52 AM

Well, you could make a base case so that the first thing that you check is if position is larger than the length of the lists and return True if that's the case. In code this looks like:
```def isListEqual(lstOne, lstTwo, position):
if len(lstOne) != len(lstTwo):
return False

if len(lstOne) == position:
return True

if lstOne[position] == lstTwo[position]:
return isListEqual(lstOne, lstTwo, position+1)

```

This isn't necessarily the cleanest recursion code, but it works.

### #3 jon.kiparsky

• Pancakes!

Reputation: 8771
• Posts: 15,099
• Joined: 19-March 11

## Re: Playing with Python - recursion

Posted 17 October 2012 - 09:05 AM

simple recursion for list equality would look like this:

if list1 isEmpty return list2 isEmpty
if list2 isEmpty return false
return false

Implementation is language-specific, but the idea is the same. In python you'd pass slices down: list1.head would be list1[0], list1.tail would be list1[1:] In a lisp you'd use car and cdr. Same idea, though.

I don't think there's a native isEmpty call in python, but you can use len(list)==0 or something for that.

This post has been edited by jon.kiparsky: 17 October 2012 - 11:00 AM

### #4 baavgai

• Dreaming Coder

Reputation: 6301
• Posts: 13,467
• Joined: 16-October 07

## Re: Playing with Python - recursion

Posted 17 October 2012 - 09:15 AM

```def isListEqual(lstOne, lstTwo, position):
# this is fine
if len(lstOne) != len(lstTwo):
return False

# this is pointless, why are you doing it?
# length = len(lstOne)

# you get here, but you've never checked if either list is 0
# so either of these could fail
if lstOne[position] == lstTwo[position]:
# what does this do?
# you aren't returning anything
# so this is also pointless
# note passing "position = position + 1" is simply wrong
isListEqual(lstOne, lstTwo, position = position + 1)

return False

```

### #5 atraub

• Pythoneer

Reputation: 823
• Posts: 2,198
• Joined: 23-December 08

## Re: Playing with Python - recursion

Posted 17 October 2012 - 09:26 AM

First off, SegFaulty is on the right track but this code has some other minor issues.

on line 7, the output of the recursive call isn't returned.

Checking if the two lists are the same length is good, but doing it on every recursive call is bad. I like nested functions in recursion for this sort of thing.

On your initial run, position will always be 0, so make that a default parameter... or don't include it in the parameters of the outer function if you decide to use a subfunction... or do both :-P

line 5 is useless.

Here's my take on this:
Spoiler

EDIT:
passing position = position + 1 into sub_isListEqual(lstOne, lstTwo, position = position + 1)is not simply wrong. It's unusual, but it does do precisely what it's intended to do.

This post has been edited by atraub: 17 October 2012 - 09:38 AM

### #6 darek9576

• D.I.C Lover

Reputation: 202
• Posts: 1,705
• Joined: 13-March 10

## Re: Playing with Python - recursion

Posted 17 October 2012 - 10:23 AM

Sweet.
@baavgai: I know that all roads lead to False but before False is reached for equal lists, the exception will be thrown. I am just playing with the language. I did not know how to exit the function with True.
I agree, line 5 is not used. My bad.

@atraub: does the method of defining a function within a function have any Pythonic name? I googled that and i got closures as a result. Is that what it's called (oficially)? I want to read about it since i want to get better at Python.

Thanks all.

This post has been edited by darek9576: 17 October 2012 - 10:25 AM

### #7 baavgai

• Dreaming Coder

Reputation: 6301
• Posts: 13,467
• Joined: 16-October 07

## Re: Playing with Python - recursion

Posted 17 October 2012 - 11:22 AM

darek9576, on 17 October 2012 - 01:23 PM, said:

@baavgai: I know that all roads lead to False but before False is reached for equal lists, the exception will be thrown.

The problem is you don't return the result of your function you're calling recursively. You also don't check for the end.

Trace it. e.g.
```>>> def isListEqual(lstOne, lstTwo, position):
...     print("position=", position)
...     if len(lstOne) != len(lstTwo):
...         return False
...
...     length = len(lstOne)
...     if lstOne[position] == lstTwo[position]:
...         isListEqual(lstOne, lstTwo, position = position + 1)
...
...     return False
...
>>> one = [1,2,3,4,5]
>>> two = [1,2,3,4,5]
>>>
>>> isListEqual(one, two, 0)
('position=', 0)
('position=', 1)
('position=', 2)
('position=', 3)
('position=', 4)
('position=', 5)
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
File "<stdin>", line 8, in isListEqual
File "<stdin>", line 8, in isListEqual
File "<stdin>", line 8, in isListEqual
File "<stdin>", line 8, in isListEqual
File "<stdin>", line 8, in isListEqual
File "<stdin>", line 7, in isListEqual
IndexError: list index out of range
>>>

```

Hmm... your len is 5, so 0..4. Checking position 5. Well, that's what we'd expect.

How to fix it? Check if position is < len of each list.

Since there's already examples on the table, let's fix yours up:
```# don't make me pass position on the first call
# give it a starting value
def isListEqual(lstOne, lstTwo, position = 0):
# it's a shame we have to check this every time
# no way around it
if len(lstOne) != len(lstTwo):
return False

# this is the one you're missing
if position==len(lstOne):
# we made it past the end
# we win
return True

if not lstOne[position] == lstTwo[position]:
# don't bother going any farther
return False

# NOW, the magic recursion
# note the return
return isListEqual(lstOne, lstTwo, position + 1)

```

There are a number of ways to skin this cat, of course. Here's how I'd do it:
```def isListEqual(lstOne, lstTwo): # we don't need no position, a list is a list
# the ==[] is a check for empty
# a len()==0 is all a check, but this is more listy
if lstOne==[] and lstTwo==[]: # We've reached the end, True
return True
if lstOne==[] or lstTwo==[]: # one reached the end, but not both, false
return False
# now the clever recursive return
# if the first part, lstOne[0]==lstTwo[0], is false, we'll stop and return false
# however, if the first part is true, we call ourselves
# here, we use a list operation to pass each list with the first item removed
return lstOne[0]==lstTwo[0] and isListEqual(lstOne[1:], lstTwo[1:])

```

### #8 atraub

• Pythoneer

Reputation: 823
• Posts: 2,198
• Joined: 23-December 08

## Re: Playing with Python - recursion

Posted 17 October 2012 - 03:05 PM

I've just called them nested functions

Admittedly, most people don't use them extremely often.

This post has been edited by atraub: 17 October 2012 - 03:10 PM