Click here to Skip to main content
15,867,686 members
Please Sign up or sign in to vote.
0.00/5 (No votes)
See more:
So as homework, I need to implement the reverseRec function recursively. I can't use any loops, but must use the putBack function in it and the function needs to return something, which makes everything unnecessarily complicated.

C++
#include "stdio.h"
#include "stdlib.h"

int length(char *s) {
  int n = 0;
  while(*s != '\0') {
    n++;
    s++;
  }
  return n;
}

void copy(char* s, int n, char* t) {
  int i = 0;
  while(i < n) {
    t[i] = s[i];
    i++;
  }
}

char* putBack(char* s, char c) {
  const int n =  length(s);
  char* r = malloc(sizeof(char) * (n+2));
  copy(s, n, r);
  r[n] = c;
  r[n+1] = '\0';
  return r;
}

char* reverseRec(char *s){     

    if(*s){                   
        reverseRec(s+1);
        s = putBack(s, *(s-1));           //???
    }
    return s;
}


int main() {
printf("%s", reverseRec("ABC"));
}


What I have tried:

So after the recursion reaches the end of the string, it returns. If e.g. the string is "ABC", then it goes ABC-->BC-->C-->/0-->C-->BC-->ABC. My idea was, that I somehow save the beginning of the string (*s) of every returning recusion, and add them together with the putBack funcion to CBA. But I think this can't work, since it's a recursion, which means I can't save anything from any recursion depth, because it would be overritten, right? I feel like I'm missing something about how recursions and buffers work in C, but idk.
Posted
Updated 21-May-20 6:44am

 
Share this answer
 
When recursion is explicit your task than you will need to use the divide and conquer algorithm.

A possible solution may be that you call your swap function with the first and last char* of your string, check that their distance is greater than 1 (uneven case) than swap and call recursive the function with the next swap pair.

C++
void swap(char *first, char* last)
{
  int diff = last - first;

  if( diff > 1 ) {
    swap(first + 1, last - 1);
  }
  //swap 
  char c = *first;
  *last = *last;
  *first= c;
}
I hope you understand the principle.
 
Share this answer
 
example input string "12345" must become "54321"
your prof gave you a hint about. The recursiveness breaks the input string into smaller parts and then builds then 1 by 1 together. This means the amount of "recursive steps" are five for the input string "12345"

Hint 1: the inputs for reverseRec( ) are
input 1: "12345"
input 2: "2345"
input 3: "345"
input 4: "45"
input 5: "5"

Hint 2: the outputs from each reverseRec( ) are
output 1: "54321"
output 2: "5432"
output 3: "543"
output 4: "54"
output 5: "5"

Hint 3: since reverseRec( ) calls itself, it returns itself a value. This value can be used.
reverseRec 1( string ) gets "5434"
reverseRec 2( string ) gets "543" ( the called reverseRec3 returns "543" )
reverseRec 3( string ) gets "54" ( the called reverseRec4 returns "54" )
reverseRec 4( string ) gets "5" ( the called reverseRec5 returns "5" )
reverseRec 5( string ) gets nothing ( no next reverseRec was called to get a value from)

Hint 4: now you got a set of information and a missing objective
given information (inputs) from Hint 1:
given information (outputs) from Hint 2:
returned value from Hint 3:

reverseRec 1( string ) gets "5434", should return "54321", given input string "12345"
reverseRec 2( string ) gets "543", should return "5432", given input string "2345"
reverseRec 3( string ) gets "54", should return "543", given input string "345"
reverseRec 4( string ) gets "5", should return "54", given input string "45"
reverseRec 5( string ) gets nothing, returns 5, given input "5"

Hint 5: the missing objective
you must create the [should return "output"] for step 4,3,2,1
you got the return value, the input string, and putBack


The information is 80% of the work ;) now sit down and test some ideas with putback,
or use the debugger to go step by step to see what is happening when.


reverseRec( ) {
// recursive magic
 
Share this answer
 

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)



CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900