1

I'm trying to solve a problem using recursion that would be pretty verbose if I used 'if' statements. I'm looking to see how many times a CONST = 50 is in n. I want to return the number of occurrences that 50 is in n. I know it's straight forward but I want to use recursion to accomplish this, that is not straight forward to me. The conditions are like:

0 < n == 50 -> 1 instance
50 < n <= 100 -> 2 instance
100 < n <= 150 -> 3 instance
150 < n <= 200 -> 4 instance
200 < n <= 250 -> 5 instance
...
...
...

Below is what I started, but I got stuck:

def num_of_times(n)
""" (int) => int 
when n is entered count 1 for every 50 found. If any number is over 50, yet does not
equal another 50 (e.g. n = 60; 60 - 50 = 10; 50 -> 1; 10 -> 1) will call for a count, which would be a count of 2 in this case.

>>>num_of_times(60)
2
>>>num_of_times(200)
4
"""
    count = 0

    if n > 0 and n == 50:
        count += 1
    elif n > 50:
       """ Here is where my thinking is going to sleep"""
       ...
       ...
       ...

Thanks in advance for any help offered.

Improve this question
2
  • 4
    Why not use integer division? 1 + ((n-1) / 50) Commented Apr 8, 2013 at 17:27
  • 2
    or math.ceil(n/50.0). Commented Apr 8, 2013 at 17:29

3 Answers 3

Reset to default
2

For this specific problem, you should just use a division:

count = n // 50 + 1

(Note the use of double slashes, instead of just "/" - that asures you that even on Python 3 an integer division is performed, with the result roudned down, instead of giving you a floating point value as the result)

Now, about recursion - it is not the prefered way of solving problems in Python - recusive functions that might have the same cost of an itnerative "for loop" in an "optimized for funciton calls" language, like scheme, is better of dealt with a for or while loop.

Keeping with this example - and leading to recursion - you need to change both your data input, and your results at each interation - so that when your data requires no logner processing, you yiled the final result:

count = 0
while n >= 50:
   count += 1
   n -= 50

And from here, it is easier to check what should a recursive approach do: each sucessive call should receive the modified values for "n" and for "count" than the previous iteration. You can take advantage of Python's optional parameters syntax so that the first call to the function does not have to add the "count" parameter:

def num_of_times(n, count=0):
    if n < 50:
        return count
    return num_of_times(n - 50, count + 1)

This is limited to n = about 50000 in Python, due to a call-stack depth set on the interpreter - and the default maximum recusion depth set to 1000. You can change that number by setting it in the sys module - but that is definetelly not the recomended approach in Python - both for the overhead of function calls, and for the higher level facilities of the whie and for constructs. It is obviously ok for some functions that would recurse 2 - 100 times, like ones processing paths to files, URL parts, and so on - especially if the function ends up being more readable than an interactive counterpart.

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

2 Comments

Count is not required see my version posted before this one
@Yoriz: indeed - I have my mind in a "tail-recusion-elimination" mindset whenever I see code like this. When doing that one should not have any operations left on the recurring function when the tail call is made. I have a Python decorator for that: metapython.blogspot.com.br/2010/11/…
1

Recursion seems to be the least useful way to do this, but if recursion is required, try this:

def num_of_times(n):
    if n > 0 and n <= 50:
        return 1
    elif n > 50:
        return 1+num_of_times(n - 50)
    else:
        return 0
Improve this answer

4 Comments

This is incorrect it returns 1 for n between 0 and 49 see my version for a simpler correct solution
But see OP's requirement statement: 0 < n == 50 -> 1 instance and num_of_times(60) == 2.
Hmm his questions is confusing as it states in the text 'I'm looking to see how many times a CONST = 50 is in n. I want to return the number of occurrences that 50 is in n' and then gives an example >>>num_of_times(60) 2 which none of the methods given gets right
I take that back yours is giving 2 for 60
0

How about.

def num_of_times(n):
    if n < 50:
        return 0
    return 1 + num_of_times(n - 50)

If the result you are after is not 1 for every dvisable of 50 and actually between 1 and 50 = 1, between 51 and 100 = 2 etc , then

def num_of_times(n):
    if n <= 0:
        return 0
    elif n < 51:
        return 1
    return 1 + num_of_times(n - 50)
Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.