Jump to content


Check out our Community Blogs

Register and join over 40,000 other developers!


Recent Status Updates

View All Updates

Photo
- - - - -

[SOLVED] Using a recursive function to return the position of the last nonblank character of a string.

string recursive

  • This topic is locked This topic is locked
5 replies to this topic

#1 Yuriy M

Yuriy M

    CC Addict

  • Advanced Member
  • PipPipPipPipPip
  • 126 posts

Posted 04 September 2012 - 06:06 PM

Hi guys. I'm having trouble with another program. This one involves returning the numerical position of the last nonblank character of a string. I can get the program to work iteratively but recursively is another matter. Here is my code:

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <ctype.h>
int position(const char *);
int main(void)
{
    char string[100];
    int  pos_result;
	
    printf("\nEnter a string: ");
    gets(string);
	
    pos_result = position(string);
   
    printf("\nThe position of the last nonblank character of the string is %d.\n", pos_result);
    return 0;
}
int position(const char *str)
{
    int pos_no = 0,
	    pos_counter = strlen(str);
	   
/*   for (pos_counter = curr_chars; pos_counter >= 0; pos_counter--)
    {
	 if (isalpha(str[pos_counter]) || isdigit(str[pos_counter]))
	 {
	  pos_no = pos_counter;
	  break;
	 }
    }
*/
    if (str[0] == '\0')
	 exit(0);
    else if (pos_counter >= 0 && isspace(str[pos_counter]))
	 position(str++);
    else
	 pos_no = pos_counter;
   
    return pos_no;
}  
The section of code that is commented is the iterative version of the function which performs the operation perfectly. However, I'm going around in circles just trying to get the recursive version working. What am I doing wrong? :S
  • 0
For $1000: Something that is a miserable pile of secrets.

#2 kernelcoder

kernelcoder

    CC Devotee

  • Expert Member
  • PipPipPipPipPipPip
  • 990 posts
  • Location:Dhaka
  • Programming Language:C, Java, C++, C#, Visual Basic .NET
  • Learning:Objective-C, PHP, Python, Delphi/Object Pascal

Posted 04 September 2012 - 06:16 PM

I have not debugged your code but just looking into your code it seems there are problems. I think the following changes will fix the problem.
int recursive(const char *str, int currentIndex)
{
if (currentIndex < 0)
return -1;
else if (isalpha(str[currentIndex]) || isdigit(str[currentIndex]))
return currentIndex;
else
return recursive(str, currentIndex - 1);
}

int position(const char *str)
{
return recursive(str, strlen(str) - 1);
}

If this works correctly, I'll explain what are the problems in your code in a next comment (or I'll just edit this comment).
  • 0

#3 Yuriy M

Yuriy M

    CC Addict

  • Advanced Member
  • PipPipPipPipPip
  • 126 posts

Posted 04 September 2012 - 06:46 PM

That definitely worked. I wasn't aware that a second function would've been needed. :unsure:
  • 0
For $1000: Something that is a miserable pile of secrets.

#4 kernelcoder

kernelcoder

    CC Devotee

  • Expert Member
  • PipPipPipPipPipPip
  • 990 posts
  • Location:Dhaka
  • Programming Language:C, Java, C++, C#, Visual Basic .NET
  • Learning:Objective-C, PHP, Python, Delphi/Object Pascal

Posted 04 September 2012 - 06:56 PM

Well, by definition a recursive function must have one or more 'non-recursive' case (which called base cases and for which the function will return without calling itself) and must have one or more 'recursive' case (for which function will call itself).

Now your problem is: find the last place in a string that has a 'non space' character.

The Algorithm is: We need to start searching from the end of the string to look for a 'non space' character.

Now if we want to convert the algorithm in a recursive one, there are two non-recursive case and one recursive case --
Non Recursive Cases
  • If the current character is a 'non-space' character, return the current character position.
  • If all the characters are searched in that string, return -1
Recursive Cases
  • If the current character is a 'space' character, search for a 'non space' character starting the starting from the 'left immediate' character (this is the same solution as our global solution but the only difference is that our global solution starts searching from the end character of the string)

Now again let us look in the code.
int recursive(const char *str, int currentIndex)
{
if (currentIndex < 0) // Non recursive case
return -1;
else if (isalpha(str[currentIndex]) || isdigit(str[currentIndex])) // Non recursive case
return currentIndex;
else
return recursive(str, currentIndex - 1); // Recursive case
}

int position(const char *str)
{
return recursive(str, strlen(str) - 1);
}

So to make the 'Recursive' case and our global solution general, we wrote a function 'recursive' which takes an extra argument (than our input string) which is the current character index to be searched. We' just need to provide only the input string from the caller/user code so we created another function 'position' which in turn calls the 'recursive' function providing the last character index as the current-index for the 'recursive' function.
  • 0

#5 Yuriy M

Yuriy M

    CC Addict

  • Advanced Member
  • PipPipPipPipPip
  • 126 posts

Posted 04 September 2012 - 07:51 PM

That's quite a mouthful. But I will still memorize this bit of code for the future so that I will be more prepared should this matter arise again. Thanks.for the help! :)
  • 0
For $1000: Something that is a miserable pile of secrets.

#6 Roger

Roger

    Skadoosh!

  • Administrator
  • 1222 posts
  • Programming Language:C, PHP
  • Learning:Others

Posted 05 September 2012 - 10:20 AM

This topic has been marked as SOLVED. If you have a similar question or topic, you can go back to the subforum and start a new topic to continue discussions.
  • 0

New around here? Click here to register and start participating in under a minute?

Or do a quick search and you may find the answer you're looking for.






Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download