recursion - Why do recursive function in C returns control to main, not previous call?

Question

I'm writing converter from classic expression notation to Reverse Polish notation. Current piece of code is wrong (works, but does something different than converting), but when I was debugging it I have discovered strange behavior of return.

Call:

str_to_spol( "(2+3)*(5+6)", a);

void str_to_spol(char * str, char * spol)
{
    static int pos = 0;
    while(str[pos]!='')
    {
        if (str[pos]=='(') 
        {
            pos++;
            return str_to_spol(str,spol);
            pos++;
        }
        else if(str[pos]==')')
            return;
        else
        {
            spol[pos]=str[pos];
            printf("%c ", str[pos]);
            pos++;
        }
    }
}

On the fisrt symbol '(' function calls itself, we have two functions. Second function works until it meets ')', then it returns control to the end of function, not inside if! Why is it so?

In other words output should be: 2 + 3 * 5 - 6

And the output is: 2 + 3

I'm using gcc 4.8.2

Answer 1

You have the second pos++ in the wrong place. It should be before the next return. What's happening is that on return having detected ')', the same ')' is detected by every caller, and the call stack drops to the bottom.

There is also a syntax error: the function cannot return a value.

#include <stdio.h>

void str_to_spol(char * str, char * spol)
{
    static int pos = 0; 
    while(str[pos]!='')
    {
        if (str[pos]=='(') 
        {
            pos++;
            str_to_spol(str,spol);    // <<--- removed `return`
        }
        else if(str[pos]==')')
        {
            pos++;                    // <<--- moved down
            return; 
        }
        else
        {
            spol[pos]=str[pos];
            printf("%c ", str[pos]);
            pos++;
        }
    }
}

int main(void){
    char str[] = "(2+3)*(5+6)";
    char spo[50];
    str_to_spol(str, spo);
    printf("
");
    return 0;
}

Program output:

2 + 3 * 5 + 6