Python issue with program involving recursion

Question

For a course I am making a program that must involve recursion. This is what I have so far:

def words(letters, start, word):
    while (start) < (len(letters)):
        word = word + letters[start]
        print(word)
        letters = letters.replace(letters[start], "")
        start = (words(letters, start, word))
        return (start + 1)

The goal of the program is to accept a list of letters and output all possible combinations of those letters. I am not sure if the program will work, but before that, I am running into another issue. When I run this with a basic command, e.g.

words("abcd", 0, "")

(the 0 and the "" are just for starting off the command as they are necessary in the future). But when I run that, it outputs, a ab abc abcd, but then stops with an error citing the line return(start + 1) saying the start is not an integer, but a None type. When did start become a None type? And how can I keep it as an integer?

qwertynl · Accepted Answer · 2013-11-19 22:22:16Z

2

Remember to return something if the while loop doesn't get entereed (which is basically an if statement in your example):

def words(letters, start=0, word=""):
    if start < len(letters):
        word = word + letters[start]
        print(word)
        letters = letters.replace(letters[start], "")
        start = words(letters, start, word)
        return start + 1
    else:
        return 0

Also I set some default values, so you can now do this:

words(letters="abcd")

answered Nov 19, 2013 at 22:22

qwertynl

3,9331 gold badge24 silver badges43 bronze badges

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

2 Comments

user2832964 Over a year ago

The problem with the if statement is that each level needs to be run through several times to output each option, e.g. the word can start with a, b, c, or d, but if you use an if statement, only "abcd" will be outputted.

qwertynl Over a year ago

@user2832964 your example is basically an if statement. It returns on the first iteration.

inspectorG4dget · Accepted Answer · 2013-11-19 22:22:43Z

When you return, you return an int. However, you only do so within your while loop, i.e. when start < len(letters). If that condition is not met, your function returns nothing, i.e. NoneType.
This is why eventually, in your while loop, start becomes a NoneType, which leads to your error.

You could do something like this:

def words(letters, soFar=''):
  if not letters:
    print(soFar)
  else:
    for i,char in enumerate(letters):
      words(letters[:i]+letters[i+1:], soFar+char)

Collectives™ on Stack Overflow

Python issue with program involving recursion

2 Answers 2

2 Comments

Comments

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

2 Comments

Comments

Related