Рекурсивная функция, команда после отзыва

Question

Я слежу за pdf, чтобы изучить рекурсию и манипуляции со строками, и я наткнулся на это .. У меня обычно есть понимание того, как будет вести себя рекурсивная функция (все еще не так хорошо), но я не могу понять это. Это переворачивает строку. Ну, печатает это наоборот.

void reverse(const char *const sptr);

int main()
{

char sentence[80];
printf("Enter a line of text:\n");
gets(sentence);

printf("\nThe reversed version:\n");
reverse(sentence);
puts("");


return 0;
}

void reverse(const char *const sptr)
{
    if(sptr[0] == '\0')
    {
        return;
    }
    else{
        reverse(&sptr[1]);
        putchar(sptr[0]);
    }
}

Я не очень понимаю, как работает putchar в этом случае. Кто-нибудь может мне это объяснить? Я предполагаю, что это не только для putchar, как ведет себя функция, когда другая командная строка пишется «после» вызова функции?

Answer 1

Как все остальные говорят, это просто.

Но лучшее, что нужно объяснить, это увидеть, как это работает при добавлении некоторого журнала в ваш C-код.

#include "pch.h"
#include <stdio.h>
#include <stdlib.h>

void reverse(const char *const sptr);
void openTraceFile();
void closeTraceFile();
void enterFunction();
void exitFunction();
void writeMessage(const char* s);

int main()
    {
    char sentence[80];
    printf("Enter a line of text:\n");
    //gets(sentence);
    fgets(sentence, 80, stdin);

    openTraceFile();

    printf("\nThe reversed version:\n");
    reverse(sentence);
    puts("");

    closeTraceFile();

    return 0;
    }

static FILE* logfile;
static int iNrSpaces = 0;

void reverse(const char *const sptr)
    {
    enterFunction();

    if (sptr[0] == '\0')
        {
        writeMessage("end of string");
        exitFunction();
        return;
        }

    reverse(&sptr[1]);

    putchar(sptr[0]);

    char s[80];
    sprintf(s,"putchar( %c )", sptr[0]);
    writeMessage(s);

    exitFunction();
    }

void openTraceFile()
    {
    logfile = fopen("reverse.log", "w");

    if (logfile == NULL)
        {
        printf("Error! Could not open file\n");
        exit(-1);
        }


void closeTraceFile()
    {
    fclose(logfile);
    }

void enterFunction()
    {
    writeMessage(">> reverse()");
    iNrSpaces += 4;
    writeMessage("{");
    }

void exitFunction()
    {
    writeMessage("}");
    iNrSpaces -= 4;
    }

void writeMessage(const char* s)
    {
    for (int i = 0; i < iNrSpaces; i++)
        {
        fputc(' ',logfile);
        }
    fprintf(logfile, s);
    fputc('\n', logfile);
    }

Когда вы запустите эту программу при вводе «справки», вы получите следующие строки в файле reverse.log.

>> reverse()
    {
    >> reverse()
        {
        >> reverse()
            {
            >> reverse()
                {
                >> reverse()
                    {
                    >> reverse()
                        {
                        end of string
                        }
                    putchar( \0 )
                    }
                putchar( p )
                }
            putchar( l )
            }
        putchar( e )
        }
    putchar( h )
    }

Если сейчас вы извлечете вызов putchar () без изменения порядка выполнения, вы получите

putchar( p ); 
putchar( l ); 
putchar( e ); 
putchar( h ); 

это перевернутая строка!

Я надеюсь, что это объяснение с помощью LOG помогло вам понять эту проблему.

Небольшое замечание: в вашем примере символ \ 0 возвращается первым!

Answer 2

Это очень просто.

Вы рекурсивно вызываете функцию со строкой в ​​качестве параметра. Каждый вызов строки на один символ короче (когда вы передаете указатель на второй char в строке. Когда он равен нулю, происходит первый возврат. Строка имеет длину 1 и это только последний символ строка. Вы печатаете ее (как вы печатаете первый символ), затем вы возвращаетесь к экземпляру, где строка была длиной 2 символа - вы печатаете его первым символом, который является вторым от конца. Затем вы возвращаете, и строка равна 3 Если вы печатаете первый символ снова, это повторяется до тех пор, пока вы не напечатаете все символы из строки в обратном порядке.

Вы вообще не нуждаетесь в операторе else, как будто условие выполнено, элемент управления никогда не достигнет этих операторов

void reverse(const char *const sptr)
{
    if(!sptr[0]) return;
    reverse(&sptr[1]);
    putchar(sptr[0]);
}

int main()
{
    reverse("Hello World");

    return 0;
}

Вы также можете добавить проверку, если параметр не NULL

void reverse(const char *const sptr)
{
    if(!sptr && sptr[0] == '\0') return;
    reverse(&sptr[1]);
    putchar(sptr[0]);
}

Answer 3

Это не имеет ничего общего с путчаром, оно имеет отношение к рекурсии.

Скажем, вы даете ей строку "1234" - или давайте назовем ее ['1','2','3','4','\0'] В первый раз вызывается реверс, он вызывается с аргументом sptr, указывающим на ['1','2','3','4','\0'];

Выполнение достигает рекурсивного вызова реверса, и на этот раз используется смещение 1, поэтому аргумент становится ['2','3','4','\0']

Процесс повторяется до тех пор, пока не будет найден '\0', и теперь функция возвращается к предыдущему вызывающему, который печатает последний символ, возвращает к предыдущему вызывающему, который печатает 2-й последний символ и так далее до тех пор, пока не будет выполнен обратный вызов сверху. достигается, который печатает первый символ, а затем существует.

Возможно, распечатка дополнительной отладочной информации облегчит понимание.

#include <stdio.h>

void reverse(const char *const sptr);

int recursion_level;

int main()
{
recursion_level=0;
    char sentence[80]="1234";
    // printf("Enter a line of text:\n");
    // gets(sentence);

    printf("\nThe reversed version:\n");
    reverse(sentence);
    puts("");
    return 0;
}

void reverse(const char *const sptr)
{
        recursion_level++;
        printf("reverse entered, recursion level:%d , sptr:%s \n",recursion_level, sptr);
        if(sptr[0] == '\0')
        {   recursion_level--;
            return;
        }
        else{
            reverse(&sptr[1]);
            putchar(sptr[0]);
        }
        printf("\n  reverse exits, recursion level:%d , \n",recursion_level);
        recursion_level--;
}

, который генерирует следующий вывод

The reversed version:                                                                                                                          
reverse entered, recursion level:1 , sptr:1234                                                                                                 
reverse entered, recursion level:2 , sptr:234                                                                                                  
reverse entered, recursion level:3 , sptr:34                                                                                                   
reverse entered, recursion level:4 , sptr:4                                                                                                    
reverse entered, recursion level:5 , sptr:                                                                                                     
4                                                                                                                                              
  reverse exits, recursion level:4 ,                                                                                                           
3                                                                                                                                              
  reverse exits, recursion level:3 ,                                                                                                           
2                                                                                                                                              
  reverse exits, recursion level:2 ,                                                                                                           
1                                                                                                                                              
  reverse exits, recursion level:1 ,  

Answer 4

это работает из-за этого:

   reverse(&sptr[1]);
   putchar(sptr[0]);

сначала вы вызываете следующие символы , затем вы печатаете первый, поэтому

• первый напечатанный символ будет последним
• затем вы возвращаетесь и пишете предыдущее существо как раз перед последним
• ...
• затем вы возвращаетесь и печатаете первый символ

&sptr[1] эквивалентен sptr + 1, так что он указывает на адрес следующего символа

---

если перевернуть строки и сделать это:

   putchar(sptr[0]);
   reverse(&sptr[1]);

вы печатаете символы в исходном порядке

---

Если вы не понимаете, просто запустите программу в пошаговом отладчике