0

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!

Improve this question
8
  • Aside from a (recursive) solution, your requirement to continue checking until it is not used, can result in a never ending program. I think there must be better ways to achieve your requirement. Commented Feb 10, 2012 at 15:42
  • This question isn't clear. When I add a value to used ? Commented Feb 10, 2012 at 15:43
  • 1
    You shouldn't use recursion unless the recursive function has a condition that will definitely be reached that will unwind the stack. To the best of my knowledge, Python does not have tail call optimization, so an open-ended recursive call like this is an invitation to (of all things) a Stack Overflow. Commented Feb 10, 2012 at 15:45
  • 2
    I don't know what f is trying to do, so I can't be of too much help, but one possible area of trouble is where you return new in the else clause. That would return right away. And since you don't return f() in the if i in used block, you always return None Commented Feb 10, 2012 at 15:47
  • 1
    Google "recursion example Python". Commented Feb 10, 2012 at 16:14

5 Answers 5

Reset to default
2

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.

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

Comments

0

You should add parameters of the function, and transfer proper parameter to recursive function calls.

For example:

def f(new, used, i):
Improve this answer

Comments

0

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
Improve this answer

Comments

0

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.

Improve this answer

Comments

0

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)
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.