Концепция обращения строки с использованием рекурсивной функции

Question

void foo3(char *x) 
{
  if (!*x) return;
  foo3(x+1);
  printf("%c ",*x);
}

Если, например, x указывает на массив ar[]="abc", почему он печатает "cba"? Почему он даже печатает, если будет просто повторять ввод функции снова и снова, пока if не станет true, тогда он вернется.

Как это печатать?

Answer 1

@ cdlane имеет точку. Этот пример с двумя printf поможет вам понять механизм, стоящий за recusrion.

#include <stdio.h>
void foo3(char *x)
{
    printf("%c=\n",*x);
    if (*x=='\0') return;
    foo3(x+1);
    printf("%c ",*x);
}
int main(void)
{
    foo3("abc");
    return 0;
}

Answer 2

Стек вызовов будет выглядеть следующим образом (псевдокод), который должен показать, как и почему он печатает 'cba'.

x - это массив в стиле C 'a', 'b', 'c', '\ 0'

call foo3(x)
    call foo3(x+1)
        call foo3(x+2)
            call foo3(x+3)
            return to foo3(x+2)
        print(x+2) 'c'
        return to foo3(x+1)
    print(x+1) 'b'
    return to foo3(x)
print(x) 'a'
return to calling program

Answer 3

Мы можем извлечь общее практическое правило из этого: если вы обрабатываете некоторые данные, а затем повторяетесь, вы работаете с данными спереди назад; если вы повторяете, а затем обрабатываете некоторые данные, вы работаете с данными задом наперед. Вы можете увидеть это, если перевернуть последние две строки:

void foo3(char *x) 
{
    if (!*x) return;
    printf("%c ", *x);
    foo3(x + 1);
}

Данные поступают в исходном порядке, так как мы сейчас обрабатываем некоторые данные и затем возвращаемся.

Answer 4

Если вы вызываете foo3("hi"), первое, что он делает, это смотрит на 'h', на который указывает параметр x. Так как это не ноль, он вызывает foo3("i") - это означает, что он передает адрес остальной части строки .

foo3("i") смотрит на 'i', видит, что он ненулевой, и вызывает foo3("") - технически он передает адрес нулевого терминатора в исходную строку.

foo3("") смотрит на нулевой терминатор и возвращает.

foo3("i") печатает 'i' и возвращает.

foo3("hi") печатает 'h'.

Функция работает, потому что она делает рекурсивный вызов перед печатью «текущего символа», так что остальная часть строки будет напечатана перед ним.