# 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)
``````

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.

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.