7 Replies - 1441 Views - Last Post: 17 October 2012 - 03:05 PM Rate Topic: -----

#1 darek9576  Icon User is offline

  • D.I.C Lover

Reputation: 198
  • View blog
  • Posts: 1,672
  • 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  Icon User is offline

  • New D.I.C Head
  • member icon

Reputation: 14
  • View blog
  • 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.
Was This Post Helpful? 1
  • +
  • -

#3 jon.kiparsky  Icon User is offline

  • Pancakes!
  • member icon


Reputation: 7293
  • View blog
  • Posts: 12,120
  • 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
if list1.head == list2.head return areEqual?(list1.tail, list2.tail)
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

Was This Post Helpful? 1
  • +
  • -

#4 baavgai  Icon User is offline

  • Dreaming Coder
  • member icon

Reputation: 5643
  • View blog
  • Posts: 12,359
  • 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)

	# all roads return false
	return False


Was This Post Helpful? 0
  • +
  • -

#5 atraub  Icon User is offline

  • Pythoneer
  • member icon

Reputation: 756
  • View blog
  • Posts: 1,990
  • 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

Was This Post Helpful? 2
  • +
  • -

#6 darek9576  Icon User is offline

  • D.I.C Lover

Reputation: 198
  • View blog
  • Posts: 1,672
  • 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

Was This Post Helpful? 0
  • +
  • -

#7 baavgai  Icon User is offline

  • Dreaming Coder
  • member icon

Reputation: 5643
  • View blog
  • Posts: 12,359
  • Joined: 16-October 07

Re: Playing with Python - recursion

Posted 17 October 2012 - 11:22 AM

View Postdarek9576, 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:])


Was This Post Helpful? 1
  • +
  • -

#8 atraub  Icon User is offline

  • Pythoneer
  • member icon

Reputation: 756
  • View blog
  • Posts: 1,990
  • 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

Was This Post Helpful? 0
  • +
  • -

Page 1 of 1