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 preconditions 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

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 at1
, and if that fails, try starting at2
, 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 becur_count
to avoid confusion.cur_count
will get decremented every recursive call, andoriginal_count
will simply be an invariant, which is equal to the originalcount
passed in tofindStartRec
(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
andoriginal_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 thesequence
we're tracking is 0. The second subcase is whencur_count != original_count
, sosequence
should be defined by our previous recursive call. Furthermore, we need to decrement thecur_count
by one, since we've just updated thesequence
. So, we'll write down these two cases for modifying thesequence
: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_count1, # 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_count1, # 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.