reverse a word using recursion

Question

I am trying to reverse a word using recursion in c and i got upto this.

#include<stdio.h>

void reverse(char *a){
    if(*a){
        reverse(a+1);
        printf("%c",*a);
    }
}

int main() {
    char a[] = "i like this program very much";
    reverse(a); // i ekil siht margorp yrev 
    return 0;
}

Suppose the input string is i like this program very much. The function should change the string to much very program this like i

Algorithm:

1) Reverse the individual words, we get the below string.
     "i ekil siht margorp yrev hcum"
2) Reverse the whole string from start to end and you get the desired output.
     "much very program this like i"

I have successfully completed up-to step 1 and i am not sure how to proceed further. Please help.

You've "completed" step 2, not step 1. But a big first step would be to store the reversed string in memory, instead of printing it out. — Bill Lynch, Aug 06 '14 at 15:28
@icepack: I agree. Currently, the output is to stdout. It would probably be helpful if the original poster learned how to store the result to __any__ piece of memory that was accessible by the program. — Bill Lynch, Aug 06 '14 at 15:34
Duplicate: http://stackoverflow.com/questions/198199/how-do-you-reverse-a-string-in-place-in-c-or-c — Adrian, Aug 06 '14 at 16:08

score 1 · Answer 1 · answered Aug 06 '14 at 15:36

To help you out without giving too much away, I think your algorithm is too complicated. Instead of reversing individual words and then reversing the whole string, consider splitting the string into an array of strings with space as a delimiter. Then simply reverse the array.

The way to do this in C is a little bit odd; since you already use char arrays as strings, you actually need to make an array of char arrays. For example:

char a[] = "i like this program very much";

actually means

a = ['i', ' ', 'l', 'i', 'k', 'e', ' ', ... , 'c', 'h']

So, you want to create an array of char arrays so it now looks like this:

new_array = [['i'], ['l', 'i', 'k', 'e'], ... ['m', 'u', 'c', 'h']]

Then all you need to do is print the new array backwards, and you've got the output you want!

score 0 · Answer 2 · answered Aug 06 '14 at 16:05

The program for outputting the words in reverse has a very similar structure to the program you already have. Instead of making a recursive call at each individual character, though, make a recursive call at each word. Then instead of printing the character after your recursive call, you print the word. The recursion stops when you have reached the end of the string, indicating you have found the last word.

In pseudo-code:

reverse_words(string a)
    start_of_word = a;
    a = end_of_word(a);
    if (a is not at end of string)
        reverse_words(a)
    print start_of_word up to a

score 0 · Accepted Answer · answered Aug 06 '14 at 17:55

#include <stdio.h>
#include <ctype.h>

void swap(char *a, char *b){
    char wk = *a;
    *a = *b;
    *b = wk;
}

void strpartrev(char *top, char *tail){
    while(top < tail)
        swap(top++, tail--);
}

void step1(char *a){
    while(isspace(*a))
        ++a;
    if(!*a)
        return;
    char *top =a;
    while(a[1] && !isspace(a[1]))
        ++a;
    char *tail = a;
    strpartrev(top, tail);
    step1(a+1);
}

int step2(char *str, int pos){
    char ch = str[pos];
    return (ch == '\0')? 0 : ((str[pos=step2(str, ++pos)]=ch), ++pos);
}

void reverse(char *a){
    step1(a);
    step2(a, 0);
}

int main() {
    char a[] = "i like this program very much";
    reverse(a);
    puts(a);//much very program this like i
    return 0;
}

score 0 · Answer 4 · answered Aug 06 '14 at 18:20

#include <stdio.h>
#include <string.h>

// copy substring of str from [start] to [first occurance of ' '] into buf
void substr(char *str, int start, char* buf){
    int end, strLength = strlen(str);
    end = start;
    do{
        if(str[end-1] == ' ' || end == strLength){
            strncpy(buf, str+(start*sizeof(char)), end-start);
            buf[end-start] = '\0';
            return;
        }
        end++;
    }while(1);
}

void reverse(char *a){
    if(strlen(a)==0){
        return;
    }
    if(*a){
        reverse(a+1);
        printf("%c",*a);
    }
}

void rec(char *str, int start){
    if(start >= strlen(str)){
        return;
    }

    char buf[32];
    substr(str, start, buf);
    rec(str, start + strlen(buf)+1);
    reverse(buf);
}

int main(int argc, char* argv[]) {
    char *str = "asd123 qwe kutu chu-chu";
    rec(str, 0);
    printf("\n");
    return 0;
}

reverse a word using recursion

4 Answers4

Linked