How to write a recursive function?

Asked

Viewed 421 times

4

I’ve been tasked with making this function recursive, but I have no idea how to do that.

int existe (int x){
    FILE *arq;
    int y;
    char buf[MAX];
    arq = fopen ("cliente.txt","r"); 
    fgets (buf,MAX,arq);
    while (!feof(arq)){
          y = atoi(strtok(buf,";"));
          if (x==y){
            fclose (arq);
            return 1;      
          }

        fgets (buf,MAX,arq);
    }
    fclose (arq);
    return 0;
c filing-cabinet recursion
  • 2

    It can’t be recursive, it’s possible to use recursion in part of it. But here’s the question, what’s the point? Are you going to get something out of it? Making an unsolicited recursion is not a good reason. The main reason to do this is when it is intended to make an appeal. If you’re having trouble doing it, then you don’t have to. Honestly, in this case, I wouldn’t waste any time trying. It is better to do without being recursive anyway. The algorithm looks sequence and not recursive. Any attempt will make the algorithm look worse.

  • 7

    @Bigown: No need to keep asking the utility... this task is clearly an exercise.

  • 2

    Is this an exercise? What are the requirements? In other words, what exactly does it need to be a recursive task? (reading and processing of a single token?)

  • Getting back to the point, SOPT works best when your question is very specific. What have you tried so far? Why do you think you can not solve the problem? Without more details the only thing we can do is give the answer ready and this is not funny :)

  • 2

    @hugomg even if it is, it is bad formulated. My answer would be "it is better to leave so than to learn to do wrong thing".

  • 5

    The OP question is missing details but I disagree that it is poorly formulated. Who passed the task simply wants to see if the OP knows how to replace loops with recursion (this is something useful to know, even if the most common is to do this conversion in the opposite direction).

  • 1

    For me the problem here is that I have no idea what this function does. There is nothing descriptive.

  • 1

    @Pablo. cliente.txt is a csv. The function in question reads the first column in each row and sees if it is x, returning 1 to find x or 0 otherwise. Probably Josh’s teacher wants him to rewrite the center of that logic with a recursive function with halting cases EOF and x==y. Well, my tip got bigger than the amount of code needed to solve this exercise :).

  • y = atoi(strtok(buf,";")); does exactly the same thing y = atoi(buf); only the latter is much more efficient :-)

Show 4 more comments

2 answers

5

Instead of offering the ready-made source code, which helps nothing if you need to write new recursive functions in the future, I’ll give you tips on how to implement a recursive function.

Any recursive function has the 4 parts below, implemented in this order:

  1. One decision to continue or stop the execution based on a control data, evaluated through a conditional expression. The control data is usually passed to the function as parameter;
  2. A body, where the work is done.
  3. A form of change the given(s) control(s): sometimes changing a counter, or more often changing which knot of the structure is the current;
  4. A way to make a backward in the flow of execution to return to the beginning: reached by invoking the function itself again.

For example, the following function prints on the screen (recursively) values of N until 1:

void countdown(int N)
{
    // 1 - Decisão para parar/continuar
    if (N < 1)
        return;

    // 2 - Corpo
    printf(“%d\n”, N);

    // 3 - Alterar o dado de controle
    N--;

    // 4 - Retrocesso no fluxo de execução
    countdown(N);    
}
  • 1

    Follow these 4 rules whenever you need to implement any recursive function.

  • 1

    +1 break the problem into pieces and follow this flow is success!

5

What repeats in the function is the cycle while

    while(!feof(arq)) {
        y = atoi(strtok(buf, ";"));
        if (x == y) {
            fclose(arq);
            return 1;
        }
        fgets(buf, MAX, arq);
    }

So this, with slight changes, needs to be replaced

int existe(int x) {
    FILE *arq;
    arq = fopen("cliente.txt", "r");

    int value = existe_rec(x, arq);

    fclose(arq);
    return value;
}

int existe_rec(int x, FILE *arq) {
    char buf[MAX];
    if (!fgets(buf, sizeof buf, arq)) return 0;
    if (atoi(buf) == x) return 1; // strtok nao é necessário
    return existe_rec(x, arq);
}

NB: error validation missing (which was also not present in the original version)!

Browser other questions tagged c filing-cabinet recursion

You are not signed in. Login or sign up in order to post.