Trouble with basic Python recursion

Question

I'm having some trouble figuring out why my code is not working, and would appreciate if someone could point out what I'm missing. It's a basic algorithm problem: given a set of distinct sorted integers, determine whether there is an element such that a[i] = i (a[3] = 3, for example).

I've tried to debug it using print statements, but it's only making one call to FindIndex and not recursing.

Here's the code:

import math

def FindIndex(SetToSearch, beginningIndex, endingIndex):
    """Searches a list of sorted integers to see if there is some a[i] == i

    Keyword Arguments:
    SetToSearch -- a list of disctinct sorted integers 
    beginningIndex -- start point of index to search
    endingIndex -- end point to search """
    # calculate midpoint of set
    midpointIndex = math.ceil((beginningIndex + endingIndex) / 2)
    midpoint = SetToSearch[int(midpointIndex)]
    print "beginningIndex: %s, endingIndex: %s" %(beginningIndex,endingIndex)
    print "midpointIndex: %s, midpoint: %s" % (midpointIndex, midpoint)
    # check whether ending index is greater then beginning index
    if (endingIndex > beginningIndex):
        return "There is no value in this set such that a[i] = i"
    if (endingIndex == beginningIndex):
        if SetToSearch[beginningIndex] == SetToSearch[endingIndex]:
            return "a[%s] is equal to %s" % [beginningIndex, beginningIndex]
    if (midpoint == midpointIndex):
        return "The value at index %d" % midpointIndex
    if (midpoint > midpointIndex):
        print "midpoint > midpointIndex evaluated to true and executed this"
        return FindIndex(SetToSearch, 0, midpointIndex)
    if (midpoint < midpointIndex):
        print "midpoint < midpointIndex evaluated to true and executed this"
        return FindIndex(SetToSearch, midpointIndex + 1, len(SetToSearch) -1)
    else:
        "Something is wrong with your program, because you should never see this!"

sampleSet = [-10, -8, -6, -5, -3, 1, 2, 3, 4, 9 ]
lastIndex = len(sampleSet) - 1

FindIndex(sampleSet,0,lastIndex)

Your syntax at the end of the else is invalid. It won't do what you think it will. — Makoto
– Makoto, Commented Sep 22, 2012 at 17:38
The first call to FindIndex returned expected results for the first print statements: beginningIndex: 0, endingIndex: 9 midpointIndex: 4.0, midpoint: -3. None of the conditionals, including the else executed. — rpmartz
– rpmartz, Commented Sep 22, 2012 at 17:40
As an aside, I don't think your math.ceil line quite works. You're using Python 2, so (beginningIndex + endingIndex) / 2 always returns an integer. If you want to round up when beginningIndex + endingIndex is odd, you could divide by 2.0 instead, to make sure it's a float. — DSM
– DSM, Commented Sep 22, 2012 at 17:42

Daniel Roseman · Accepted Answer · 2012-09-22 17:39:16Z

1

The problem isn't recursion. It's just that your first condition is always true: endingIndex is always greater than beginningIndex. That condition returns without recursion, so the function ends there.

answered Sep 22, 2012 at 17:39

Daniel Roseman

602k68 gold badges911 silver badges924 bronze badges

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

1 Comment

rpmartz Over a year ago

Thanks...careless mistake on my part.

user744186 · Accepted Answer · 2012-09-22 17:38:05Z

0

You can do that using for loop like :

def find_index_equal_value(set):
    for i in range(0, len(set)):
        val = set[i]
        if(val == i):
           print "Index matches value."

answered Sep 22, 2012 at 17:38

user744186

Comments

Useless · Accepted Answer · 2012-09-22 17:43:22Z

0

Firstly, if you can't see what happened, it's because you need to print the returned string:

print FindIndex(sampleSet,0,lastIndex)

Now, if I run it I get:

beginningIndex: 0, endingIndex: 9
midpointIndex: 4.0, midpoint: -3
There is no value in this set such that a[i] = i

which means this if matched:

# check whether ending index is greater then beginning index
if (endingIndex > beginningIndex):
    return "There is no value in this set such that a[i] = i"

... well, of course it did - endingIndex should always be greater than beginningIndex!

For future reference, did you print the string? Did you see the output line and not understand why it took that branch? Did you try stepping through the code with pdb?

answered Sep 22, 2012 at 17:43

Useless

68.5k6 gold badges100 silver badges143 bronze badges

1 Comment

rpmartz Over a year ago

No to both, but thanks for the two tips. I'll be sure to use those going forward.

athspk · Accepted Answer · 2012-09-22 22:04:55Z

0

First of all you must add return to the start of line 48.
Second, add print to start of last line.

edited Sep 22, 2012 at 22:04

athspk

6,7627 gold badges39 silver badges51 bronze badges

answered Sep 22, 2012 at 17:42

Caner Korkmaz

4074 silver badges11 bronze badges

Collectives™ on Stack Overflow

Trouble with basic Python recursion

4 Answers 4

1 Comment

Comments

1 Comment

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

1 Comment

Comments

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Related