Interpreting this recursive function (in C)

Question

I'm having trouble understanding how this reverse function works. I've tried working out what the code does step-by-step on paper, but it's not making sense to me. The best (albeit crude) interpretation I have of what the code does is this:

http://s7.postimg.org/632xhovwr/recursion_confusion.png

#include <stdio.h>
#include <string.h>
#define MAX 1000

void reverse(char s[]);

main()
{
    char str[] = "remotes";

    printf("Before: %s\n",str);
    reverse(str);
    printf("After: %s\n",str);

    system("Pause");
    return 0;
}

void reverse(char s[])
{
    static int i = 0, n;
    char c = s[i];

    if (c != '\0') {
        ++i;
        reverse(s);
        s[n-i] = c;
        --i;
    } 
    else {
        n = i;
    }
}

Normally I don't have trouble with recursive functions when the recursion is the last step of the code since you apply recursion until some terminating condition and sort of cascade backwards. But when there's code before and after the recursive call, it makes things a lot more confusing.

Answer 1

Your analysis on paper is correct - the trick is that n and i are static (each stack frame refers to the same instance of the variable) while c is allocated on the stack (so each stack frame has its own copy).

Substituting some values into your analysis, and using c, c', c'', and c''' to represent the different stack frame instances of c:

// original function call: stack frame 0
c = str[0]
i = 1

 // stack frame 1
 c' = str[1]
 i = 2

  // stack frame 2
  c'' = str[2]
  i = 3

   // stack frame 3
   c''' = str[3]
   i = 4

    // stack frame 4
    n = 4

   // unwinding: stack frame 3
   str[0] = c'''
   i = 3

  // unwinding: stack frame 2
  str[1] = c''
  i = 2

 // unwinding: stack frame 1
 str[2] = c'
 i = 1

// unwinding: stack frame 0 (original function call)
str[3] = c
i = 0

Edit: To address your comment: Don't give up on understanding recursion! Once you have a solid handle on it and can "think recursively", it's easy to write code that makes you look smarter than you are (a very useful skill!). For instance, minor refactoring of the reverse() function can create an even smaller version:

void reverse(char s[])
{
    static int i = 0;
    char c = s[i++];
    if (c) {
        reverse(s);
        s[i++] = c;
    }
    i = c ? i : (int)c;
}

So really, the original author was helping you out by being more verbose than necessary :-)

Answer 2

You must have to consider that i and n are static variables, which means that the function will keep the values among calls.

Here is output of those values:

i: 1/ n: 0
  i: 2/ n: 0
    i: 3/ n: 0
      i: 4/ n: 0
        i: 5/ n: 0
          i: 6/ n: 0
            i: 7/ n: 0

When the c variable hints the NULL value, then the function updates n value and starts to reverse the string:

            i: 7/ n: 7/ s: semotes
          i: 6/ n: 7/ s: semotes
        i: 5/ n: 7/ s: setotes
      i: 4/ n: 7/ s: setotes
    i: 3/ n: 7/ s: setomes
  i: 2/ n: 7/ s: setomes
i: 1/ n: 7/ s: setomer

Answer 3

Here i being static int keeps on incrementing with recursive calls until s[i] == '\0'. Also values of s[i] is saved in local variables 'c' in call frames.

When n == i, the reverse happens and the values from local variables 'c' are written back as i decrements.

Basically, the copies of variable 'c' across the call frames hold the values temporarily.

Answer 4

To explain the steps I've indicated three breakpoints A, B, and C. the table below shows the variables at each stage.

void reverse(char s[])
{
    static int i = 0, n;
    char c = s[i];
/* A */
    if (c != '\0') {
        ++i;
/* B */
        reverse(s);
/* C */
        s[n-i] = c;
        --i;
/* D */
    } 
    else {
        n = i;
/* E */
    }
}