# Recursive Funtion

• (2 Pages)
• 1
• 2

## 15 Replies - 990 Views - Last Post: 05 November 2017 - 08:14 AMRate Topic: //<![CDATA[ rating = new ipb.rating( 'topic_rate_', { url: 'http://www.dreamincode.net/forums/index.php?app=forums&module=ajax&section=topics&do=rateTopic&t=407348&amp;s=4fb0624cba39387867bc7f397ffe710c&md5check=' + ipb.vars['secure_hash'], cur_rating: 0, rated: 0, allow_rate: 0, multi_rate: 1, show_rate_text: true } ); //]]>

### #1 forumer444

• New D.I.C Head

Reputation: 1
• Posts: 35
• Joined: 19-September 17

# Recursive Funtion

Posted 02 November 2017 - 09:39 AM

We're studying recursion now and have to make a recursive function for homework, but I'm confused on what the description is asking for. From what I think I understand, it's asking a user to input a string to see if the string is valid, but if it's not, then what? Also, I don't get how to make a string if it's only valid between an open and closed parentheses?

*** DESCRIPTION *** Write a recursive function that takes a string as input and
returns True if the string is valid with respect to matched parentheses. To
simplify matters, begin considering that the input string has only "(" or ")"
and no other characters.

*** NOTE A *** Use 'only one parameter' to your function (the smaller version of
your string). Also, do 'not' use any parameters to 'count' or keep track of
'location' in within the string.

*** NOTE B *** Do 'not' use a 'global variable' to 'count' or otherwise keep
track of the 'location' within the string. Instead, rely on the smaller-caller.

*** EXAMPLES *** A common task in an editor application, such as 'WordPad' or
'TextEdit', is parentheses matching. For example, "(()())" is a valid string of
parentheses because each opening bracket has a corresponding closing bracket.
On the other hand, "(()" is not a valid string. Another invalid example would
be ")(", as the opening bracket should precede the closing bracket.

So this is all I have because I don't know where to start. I don't quite understand the description.

```def valid_string(a_str):
pass

# ----------------------------------------------------------------------------
# user input
input_str = input("Enter a string to see if it's valid: ")
# function call
# valid_string(input_str)

```

This post has been edited by forumer444: 02 November 2017 - 09:40 AM

Is This A Good Question/Topic? 0

## Replies To: Recursive Funtion

### #2 modi123_1

• Suitor #2

Reputation: 13965
• Posts: 55,749
• Joined: 12-June 08

## Re: Recursive Funtion

Posted 02 November 2017 - 09:45 AM

Quote

From what I think I understand, it's asking a user to input a string to see if the string is valid, but if it's not, then what?

That's the point, right?

Quote

*** DESCRIPTION *** Write a recursive function that takes a string as input and returns True if the string is valid with respect to matched parentheses.

1. Get user input.
2. Check validity
3. Tell user if valid or not.

### #3 forumer444

• New D.I.C Head

Reputation: 1
• Posts: 35
• Joined: 19-September 17

## Re: Recursive Funtion

Posted 02 November 2017 - 10:03 AM

What I don't understand is what makes a string valid exactly? It says it has to have a "(" and a ")" around the string? Is that entered by the user? Also, what recursion is going on? I don't get it. It's not as simple as returning true or not for a valid string. There's supposed to be recursion going on or something reducing the string length or something like that, but I don't know why.

### #4 modi123_1

• Suitor #2

Reputation: 13965
• Posts: 55,749
• Joined: 12-June 08

## Re: Recursive Funtion

Posted 02 November 2017 - 11:14 AM

The 'example' outlines it pretty well. Match an open bracket with a closed one, and presumably account for nesting and so on.

### #5 DK3250

• Pythonian

Reputation: 396
• Posts: 1,271
• Joined: 27-December 13

## Re: Recursive Funtion

Posted 02 November 2017 - 05:53 PM

Think of the smallest 'sub-string' that must be present if the string is valid. Remove the sub-string and test on the remainder.

### #6 forumer444

• New D.I.C Head

Reputation: 1
• Posts: 35
• Joined: 19-September 17

## Re: Recursive Funtion

Posted 03 November 2017 - 02:32 PM

Okay, I think I understood it and I got this to work. Is there any better way to write this?

```def parentheses(s):
# empty string is valid with respect to matched parentheses
if s == '':
return True

# delete all characters except for '(' and ')'
for char in s:
if not(char == '(' or char == ')'):
s = s.replace(char, '')

# find a pair of brackets
if s.find('()') != -1:
# remove all brackets and check the string for validity
return parentheses(s.replace('()', ''))
else:
# return false if the string is not empty and does not contain '()'
return False
# ----------------------------------------------------------------------------
# user input
input_str = input("Enter a string to see if it's valid: ")
print()

# print user string
print(input_str)
# print return value
print(parentheses(input_str))

```

Also, is the function name okay or should I change it to something like valid_string() or something?

### #7 forumer444

• New D.I.C Head

Reputation: 1
• Posts: 35
• Joined: 19-September 17

## Re: Recursive Funtion

Posted 03 November 2017 - 02:37 PM

Although, I guess there's not really a recursion going on, I'm just replacing the characters, so that doesn't fit the description... ?

### #8 DK3250

• Pythonian

Reputation: 396
• Posts: 1,271
• Joined: 27-December 13

## Re: Recursive Funtion

Posted 03 November 2017 - 02:55 PM

We are not 'allowed' to hand out finished code, but let me try to 'talk' you through the recursive function:
```def reduce(string):
if "()" in string:
# call the reduce() function with the 'reduced' string (parhantesis pairs removed) - this is the recursive call
elif string = "":
return True  # after removing all parhantesis pairs nothing is left, - handles also an empty string
else:
return False  # no more pairs, but still something in the string
```

The only hard thing here is line 3 that I have omitted; give it a try...
The lines 4+ will only be called when all parhantesis pairs is exhausted, i.e. the code terminates and return the result.

EDIT: Oh, I just realize, that you DO actually run recursively, - your call in line 14 does it !
Basically you solution is the same as mine (except for the coding style).
Your line 7-9 should only be run once, - before the call to the recursive function.

This post has been edited by DK3250: 03 November 2017 - 03:10 PM

### #9 forumer444

• New D.I.C Head

Reputation: 1
• Posts: 35
• Joined: 19-September 17

## Re: Recursive Funtion

Posted 03 November 2017 - 04:49 PM

DK3250, on 03 November 2017 - 02:55 PM, said:

Your line 7-9 should only be run once, - before the call to the recursive function.

So are you saying I need to change lines 7-9? I mean it's only run once right? Because after the recursion online 14, it will return True?

### #10 DK3250

• Pythonian

Reputation: 396
• Posts: 1,271
• Joined: 27-December 13

## Re: Recursive Funtion

Posted 04 November 2017 - 01:14 AM

Your comments in post #7 and #9 indicate that you don't understand the code (post #6).
Did you write the code yourself?

### #11 forumer444

• New D.I.C Head

Reputation: 1
• Posts: 35
• Joined: 19-September 17

## Re: Recursive Funtion

Posted 04 November 2017 - 02:59 PM

DK3250, on 04 November 2017 - 01:14 AM, said:

Your comments in post #7 and #9 indicate that you don't understand the code (post #6).
Did you write the code yourself?

I wrote it myself. I guess I was just experimenting and I got it to work.

I tried to write it in the format that you thought of. How's this?

```def reduce(s):
for char in s:
if not(char == '(' or char == ')'):
s = s.replace(char, '')

if '()' in s:
return reduce(s.replace('()', ''))
elif s == '':
return True
else:
return False

```

I showed my teacher and these are his exact words.

"The format looks good, except for the following: A function should do only one thing. Consequently, remove the code that deletes non-“(“ and “)” characters. One of the requirements of the problem is to not have any characters other than “(“ and “)” in the test data. Assume that it has already been done, that is, use test strings containing only open and close parentheses."

So basically, I need to move the for loop outside the function? I mean, I guess he's saying to not test the function with any other characters other than '(' and ')', so I don't need the for loop at all then... Is that right?

This post has been edited by forumer444: 04 November 2017 - 03:02 PM

### #12 forumer444

• New D.I.C Head

Reputation: 1
• Posts: 35
• Joined: 19-September 17

## Re: Recursive Funtion

Posted 04 November 2017 - 03:09 PM

So just this is fine, right?

```def reduce(s):
if '()' in s:
return reduce(s.replace('()', ''))
elif s == '':
return True
else:
return False

```

### #13 DK3250

• Pythonian

Reputation: 396
• Posts: 1,271
• Joined: 27-December 13

## Re: Recursive Funtion

Posted 04 November 2017 - 03:55 PM

Congratulations!
The function shown in post #12 is absolutely fine.

As for the for-loop, I agree it can be omitted - or run once before first call to reduce().
If the for loop is included, it can be more pythonic:
```for sign in string:
if sign not in ["(", ")"]:
string.replace(sign, "")
```

or even
```new_string = "".join([x for x in string if x in ["(", ")"]])
```

This post has been edited by DK3250: 04 November 2017 - 03:56 PM

### #14 sepp2k

• D.I.C Lover

Reputation: 2579
• Posts: 4,123
• Joined: 21-June 11

## Re: Recursive Funtion

Posted 05 November 2017 - 06:57 AM

DK3250, on 04 November 2017 - 11:55 PM, said:

If the for loop is included, it can be more pythonic:
```for sign in string:
if sign not in ["(", ")"]:
string.replace(sign, "")
```

That needs to be string = string.replace(sign, "") to do anything. But that actually makes the loop unnecessary because replace removes all occurrences of the substring from the string. So the entire loop could be replaced with string = string.replace("(", "").replace(")", "").

However that doesn't actually do what the OP wants. Like your version with join, this would simply remove all parentheses from the string without taking into account whether they match. The key to OP's approach was to only remove "()" together, if you remove the characters individually, all strings of "("s and ")"s would be valid.

The way to turn OP's approach into a loop would be like this:

```while '()' in string:
string = string.replace('()', '')
return string == ''

```

However, the assignment was to do it recursively, so that's just a thought exercise.

### #15 DK3250

• Pythonian

Reputation: 396
• Posts: 1,271
• Joined: 27-December 13

## Re: Recursive Funtion

Posted 05 November 2017 - 08:10 AM

This loop is not about parhantesis matching.
It is about removing all characters that are not '(' or ')', e.g. 'a', 'b', 'c', etc.

The parhantesis matching is covered by the recursive function.

Your point about string = string.replace(sign, "") is absolutely correct, just a blunder on my side.