Reputation:
I have been trying to understand recursion. But I don't think I've quite got a hang of it.
Here the outline for my code:
def f():
used = [anything]
new = []
while i < something:
new.append(i)
i += 1
for i in new:
if i in used:
f()
else:
return new
Now, I don't think I can use this because I'm not iterating and there is no base case. I need to keep running this program till I get a set of values (picked randomly) that are not in used. What would be the best way to achieve that? Create another function?
Any help would be greatly appreciated.
Thanks!
Upvotes: 0
Views: 214
Reputation:
If I understand correctly, you're asking for a recursive function to generate a list of pseudo-random values that are not included in another list. This recursive function will generate a size
number of pseudo-random values that do not exist in used
.
from sets import Set
import random
used = Set([1,2,3,4,5])
def f(new, size):
# Check if we have enough 'new' values that are not in the 'used' set
if len(new.difference(used)) < size:
new.add(random.randint(0,100)) # Generate a pseudo-random value and
# add it to the 'new' set
# Values are between 0-100 inclusive
# but you can change that to whatever you like
new = f(new, size) # Append our results to `new`, this will get the result set
return new.difference(used) # Return only the different
# values between the two sets
result = f(Set(), 10) # Start with a blank set and a request for a result with 10 values
print(result)
Upvotes: 0
Reputation: 35572
I think the example you are focusing on is a poor example of recursion. It is almost easier to see an iterative solution to your problem. With a perfect example of recursion, it is hard to see any other solution than a recursive solution.
One of the classic examples of recursion is navigating a tree oriented data structure.
Here is a simple example (hardly tested...):
#!/usr/bin/python
tree = {'text': '1',
'brnch': [{
'text': '1.1',
'brnch': [{
'text': '1.1.1',
'brnch': [{
'text': '1.1.1.1',
'brnch': []}]},
{'text': '1.1.2',
'brnch': []},
{'text': '1.1.3',
'brnch': []}]},
{'text': '1.2',
'brnch': []}]}
def recurse_traverse(tree):
print ' ' * recurse_traverse.level + tree['text']
for branch in tree['brnch']:
recurse_traverse.level += 1
recurse_traverse(branch)
recurse_traverse.level -= 1
if __name__ == '__main__':
import os
print "testing", os.path.abspath(__file__)
recurse_traverse.level = 1
recurse_traverse(tree)
The fine online book Think Like a Computer Scientist has more examples of recursion.
Upvotes: 0
Reputation: 1305
First of all, you need to add parameters, otherwise it's not really recursive. The gist is like this
f(x):
x-=1
if x < 5:
return x
else:
f(x)
The point of recursion is to call the function inside itself with a new parameter. x changes value every time so eventually if will drop below 5 and you'll return x (which will be 4). So it would be f(7),subtract 1, f(6), subtract 1, f(5), subtract 1, f(4), return 4.
You also don't define i or something, so you'll have an infinite loop because i will always be less, in fact, I'm surprised the code works, because neither is ever defined.
Upvotes: 2
Reputation: 14213
I think that a regular while loop will solve this problem more sensibly than a recursive call. I don't fully understand what you are trying to achieve with this code, but here it is rewritten with your tropes:
def f(used):
new = []
while len(new) == 0 :
while i < something:
new.append(i)
i += 1
for i in new:
if i in used:
new = []
break
return new
Upvotes: 0
Reputation: 8298
You should add parameters of the function, and transfer proper parameter to recursive function calls.
For example:
def f(new, used, i):
Upvotes: 0