Programming: Help With Recursive Function

[HardcoreRobot]

Yes, its for homework, so if you don't want to help thats fine.

The problem is more specific, but basically I need to write a recurisive algorithm that searches for a substring in an array and returns the leftmost occurrence if it is present.

Right now, the only thing I can think of is just using recursion to mimic a for loop and compare. Im really trying to find a way where I dont have to look at each character... any ideas? I dont need the algorithm, just suggestions.

 

[notfred]

Your function should:

check the array to see if it begins with the substring.
If so, return the string. If not, pop the first character off the array, and run again with the new shorter string.

It returns when it matches the string or the array length is 0.

 

[znaps]

You could also simulate a tree structure by doing a divide and conquer type of thing. The recursive step can test to see if the String that your dealing with has 2 characters. If it doesn't, split the String in 2 and process the left String by calling the same string recursively.

notfred's solution would be the right way to do it though 😀

 

[HardcoreRobot]

Originally posted by: notfred
Your function should:

check the array to see if it begins with the substring.
If so, return the string. If not, pop the first character off the array, and run again with the new shorter string.

It returns when it matches the string or the array length is 0.

This is basically what I had in mind initially, I was just looking for a less "linear" solution. That is how I would solve it iteratively, so I figured it wasn't the best recursive solution.

 

[notfred]

Originally posted by: HardcoreRobot

Originally posted by: notfred
Your function should:

check the array to see if it begins with the substring.
If so, return the string. If not, pop the first character off the array, and run again with the new shorter string.

It returns when it matches the string or the array length is 0.

This is basically what I had in mind initially, I was just looking for a less "linear" solution. That is how I would solve it iteratively, so I figured it wasn't the best recursive solution.

Honestly, it sounds like a stupid assignment to teach recusion, IMO. Just do it the pseudo-iteratively way.

 

[znaps]

I agree, the data structure should be a tree of some sort, not an array.

 

[notfred]

Originally posted by: znaps
I agree, the data structure should be a tree of some sort, not an array.

Who stores strings in trees?

 

[Kilrsat]

Originally posted by: notfred

Originally posted by: znaps
I agree, the data structure should be a tree of some sort, not an array.

Who stores strings in trees?

Morons who use strings to teach recursion.

 

[notfred]

Originally posted by: Kilrsat

Originally posted by: notfred

Originally posted by: znaps
I agree, the data structure should be a tree of some sort, not an array.

Who stores strings in trees?

Morons who use strings to teach recursion.

No, apparently they use arrays like everyone else.

 

[znaps]

What do you store in trees?

It's not the type of data that you're storing, it's what you want to do with it and the performance that you need that dictates the structure.