Welcome to the Treehouse Community

The Treehouse Community is a meeting place for developers, designers, and programmers of all backgrounds and skill levels to get support. Collaborate here on code errors or bugs that you need feedback on, or asking for an extra set of eyes on your latest project. Join thousands of Treehouse students and alumni in the community today. (Note: Only Treehouse students can comment or ask questions, but non-students are welcome to browse our conversations.)

Looking to learn something new?

Treehouse offers a seven day free trial for new students. Get access to thousands of hours of content and a supportive community. Start your free trial today.

Computer Science

Andrew Fellenz
Andrew Fellenz
12,170 Points

Here's how you can track the index of your recursive function in Python!

Hey Everyone,

I was going through this class, which is pretty fantastic, but I noticed that in this video, the teacher mentions that it's not possible to track the index of a recursive binary search. It takes a little extra effort, but it's most definitely possible!

Here's some code that does it. It tracks a few other things as well. Feel free to play with it and give me feedback:

"""This example is made to track the index of the value that we
are returning. To return, track, or modify any value in a
recursive manner, the value must be passed into the
function as an argument each time the function is
recursively called."""


def recursive_binary_search(values, target, index=None, count=1):

    if len(values) == 0:
        return False

    midpoint = len(values)//2
    # Showing the path traveled by the algorithm.
    print("This is our midpoint during run {}: {}"
          .format(count, values[midpoint]))

    if index is None:
        index = (len(values)//2)
    print("-- This is our index during run {}: {}\n"
          .format(count, index))

    if values[midpoint] == target:
        print("The value was {} and it took {} tries to find."
              .format(values[midpoint], count))
        print("The index was {}.".format(index))
        return True

    if values[midpoint] < target:
        new_list = values[midpoint+1:]
        index += (len(new_list)//2 + 1)
        return recursive_binary_search(new_list, target, index, count+1)

    else:
        new_list = values[:midpoint]
        # This is to ensure that the index is calculated correctly,
        #  regardless of whether the len//2 is odd or even.
        index -= (len(new_list)//2) if (len(new_list) % 2 == 0) else (len(new_list)//2 + 1)
        return recursive_binary_search(new_list, target, index, count+1)


# This calls the function on a range of numbers from 1 to 100.
# Change the second number to change the value searched for.
recursive_binary_search(range(1, 101), 99)

I'm not entirely sure why the syntax highlighting is funky on the internal comments, but try to read around them if you can.

Steven Parker
Steven Parker
216,014 Points

To get proper syntax coloring, specify the language after the 3 backticks that begin the formatted code section:

:point_right: ```python

1 Answer

Hey! Although I am beginner, I am impressed that I was able to understand 70 % of your code. Pretty good work though! I was thinking it would cool if you could let the user add the values and target. And so, you won't need to change the values each time you want to run the program. def user_input(): start = int("Please enter a number:>> ") stop = int("Please enter a second number:>> ") target = int("Please enter a target:>> ") Here is what I have tried to incorporate into the code. I don't know why it's not working XD. Any help are welcome.