Recursively finding a base sequence

findStartRec(goal, count) recursively searches forward from an initial value of 0, and returns the smallest integer value that reaches or exceeds the goal.

The pre-conditions are that goal >= 0 and count > 0. If the double (x * 2) and add 5 ( + 5) sequence starting at 0 cannot reach the goal in count steps, then try starting at 1.

Continue this process until the program finds a starting value 'N' that does reach or exceed goal in count steps, and return that start value.

Example:

findStartRec( 100, 3 ) returns '9'

Here is what I have come up with so far

def findStartRec(goal, count, sequence=0, itter=0):
    if sequence == goal and count == 0:
        print("Sequence: ", sequence, "Itter: ", itter)
        return sequence, itter
    else:
        while count > 0:
            sequence = (itter * 2) + 5
            count = count + 1
            #return findStartRec(goal, count + 1, sequence, itter)
        else:
            return findStartRec(goal, count, sequence, itter + 1)

2 answers

  • answered 2018-09-21 19:41 AlpacaJones

    I'm not quite sure what the expected outcome should be, but on line 2 of FindStartRec function, changing the "&" to "and" changes the outcome from 0,0 (0,0) to (100,4,5,0).

    Hopefully this is the outcome you expected.

  • answered 2018-09-21 20:56 Matt Messersmith

    This is clearly a HW problem, so I'll explain this pedantically. I recommend the OP or other interested parties read this if they are serious about becoming a professional programmer and/or computer scientist. The TLDR people can skip to the last section to see the final solution. I'll walk you through my thought process when solving this problem, and hopefully you can learn how to tackle recursion in the future.

    Defining the base case

    You took the right first step, which is to define the base case first. Unfortunately, you didn't quite get it right. The base case is when we have reached or exceeded the goal (i.e. when our sequence has reached or exceeded the goal). How did I know that? It says it right here in the problem statement:

    Continue this process until the program finds a starting value 'N' that does reach or exceed goal in count steps, and return that start value.

    When that happens, you'll need to return wherever you started the sequence. Here's the base case:

    if sequence >= goal: # base case, return start when we reach or exceed the goal                                                                                                                                                    
        return start
    

    Note how the function interface doesn't have a start value. We'll want to add that, which brings me to the next point, which is recursive helper functions. A common pattern across recursion is to create a helper function, because we want to pass extra parameters through our recursive calls, but we don't want to change the original interface. So we want something like this:

    def findStartRec(goal, count):
        return findStartRecHelper(goal, count, start=0)
    
    def findStartRecHelper(goal, count, start):
        if sequence >= goal: # base case (no recursion)                                                                                                                                                     
            return start
    

    Defining the recursive cases

    There are two different cases we need to consider.

    If the double (x * 2) and add 5 ( + 5) sequence starting at 0 cannot reach the goal in count steps, then try starting at 1.

    1) The first case is when our current count reaches 0. If we reach 0, then we have to try starting at 1, and if that fails, try starting at 2, and keep on repeating until we find a value that reaches or exceeds the goal.

    Continue this process until the program finds a starting value

    Notice that we also have to keep track of the original count, so we know where to start over. This implies we need another variable in the helper function, and we'll rename our count to be cur_count to avoid confusion. cur_count will get decremented every recursive call, and original_count will simply be an invariant, which is equal to the original count passed in to findStartRec (but we still need some way of keeping track of it).

    2) The second case is, naturally, when count does not equal 0. This implies we need to call our helper function recursively for the next value in the sequence. So we'll do that x * 2 + 5 thing the question alludes to. This also has subcases, but let's not worry about it till we get there.

    Defining the first recursive case:

    This is the case where cur_count == 0. Note I've added two parameters to the interface, cur_count and original_count. So now our solution looks like this:

    def findStartRec(goal, count):
        return findStartRecHelper(goal, cur_count=count, original_count=count, start=0, sequence=0)
    
    def findStartRecHelper(goal, cur_count, original_count, start, sequence):
        if sequence >= goal: # base case (no recursion)                                                                                                                                                     
            return start
        elif cur_count == 0:
            # Didn't reach the goal, but ran out of tries. Increment the start (N) and restart                                                                                                          
            return findStartRecHelper(goal=goal, # invariant                                                                                                                                            
                                      cur_count=original_count, # Restart at original_count                                                                                                         
                                      original_count=original_count, # invariant                                                                                                                        
                                      start=start+1, # try the next start                                                                                                                               
                                      sequence=0) # restart sequence at 0
    

    This is what it means to be recursive: it's a function that calls itself. findStartRecHelper is now calling itself. Note that in your original post, you have no recursion...

    Defining the second recursive case

    There two subcases inside of this second case. The first subcase is when cur_count == original_count. This implies that the sequence we're tracking is 0. The second subcase is when cur_count != original_count, so sequence should be defined by our previous recursive call. Furthermore, we need to decrement the cur_count by one, since we've just updated the sequence. So, we'll write down these two cases for modifying the sequence:

    if cur_count == original_count:
        # Sequence is 0, so use start * 2 + 5                                                                                                                                               
        sequence = start * 2 + 5
    else:
        # Sequence is not 0                                                                                                                                                                 
        sequence = sequence * 2 + 5
    # Return the next iteration                                                                                                                                                                 
    return findStartRecHelper(goal=goal, # invariant
                              cur_count=cur_count-1, # Note we've decremented by 1
                              original_count=original_count, # invariant
                              start=start,
                              sequence=sequence)
    

    Putting it all together:

    Final solution:

    def findStartRec(goal, count):
        return findStartRecHelper(goal, cur_count=count, original_count=count, start=0, sequence=0)
    
    def findStartRecHelper(goal, cur_count, original_count, start, sequence):
        if sequence >= goal: # base case (no recursion)                                                                                                                                                     
            return start
        elif cur_count == 0:
            # Didn't reach the goal, but ran out of tries. Increment the start (N) and restart                                                                                                          
            return findStartRecHelper(goal=goal, # invariant                                                                                                                                            
                                      cur_count=original_count, # Restart at original_count                                                                                                             
                                      original_count=original_count, # invariant                                                                                                                        
                                      start=start+1, # try the next start                                                                                                                               
                                      sequence=0) # restart sequence at 0                                                                                                                               
        else:
            if cur_count == original_count:
                # Sequence is 0, so use start * 2 + 5                                                                                                                                               
                sequence = start * 2 + 5
            else:
                # Sequence is not 0                                                                                                                                                                 
                sequence = sequence * 2 + 5
            # Return the next iteration                                                                                                                                                                 
            return findStartRecHelper(goal=goal, # invariant                                                                                                                                            
                                      cur_count=cur_count-1, # Note we decrement by one                                                                                                                 
                                      original_count=original_count, # invariant                                                                                                                        
                                      start=start,  
                                      sequence=sequence)
    
    print("Result: ", findStartRec(100, 3))
    

    This outputs:

    Result: 9
    

    as desired.

    HTH with the current problem and your future studies.