Просьба объяснить работу этой программы C

Question

#include<stdio.h> 

void func1(int n) 
{ 
    if(n==0) return; 
    printf("%d",n); 
    func2(n-2); 
    printf("%d",n); 
} 

void func2(int n) 
{ 
    if(n==0) return; 
    printf("%d",n); 
    func1(++n); 
    printf("%d",n); 
} 

void main() 
{ 
    func1(5); 
} 

Выход: 53423122233445

Я не понимаю, поток управления, что происходит в этом коде, ведущем к выходу выше. может кто-то объяснить. Заранее спасибо :)

Answer 1

Это становится понятным, если мы аннотируем каждый printf, чтобы мы могли узнать, из какого числа из какой части программы. Я также собираюсь изменить начальное условие на 3, чтобы мы могли пройти через все это.

#include <stdio.h> 

void func2(int); 

void func1(int n) 
{ 
    if(n==0) return; 
    printf("func1 before: %d\n",n); 
    func2(n-2); 
    printf("func1 after: %d\n",n); 
} 

void func2(int n) 
{ 
    if(n==0) return; 
    printf("func2 before: %d\n",n); 
    func1(++n); 
    printf("func2 after: %d\n",n); 
} 

int main() 
{ 
    func1(3); 
} 

Это производит:

func1 before: 3 
func2 before: 1 
func1 before: 2 
func1 after: 2 
func2 after: 2 
func1 after: 3 

1. func1 (3) печатает 3 и вызывает func2 (1).
2. func2 (1) печатает 1 и вызывает func1 (2).
3. func1 (2) печатает 2 вызова func2 (0).
4. func2 (0) немедленно возвращается.

Теперь мы попали в нижнюю часть рекурсии. На этом этапе мы создали стек вызовов функций.

1. func1 (3)
2. func2 (1)
3. func1 (2)

После func2 (0) возвращает вызов к func1 (2) поднимает, где она была прервана и мы работаем через стек снизу вверх.

5. func1 (2) печатает 2 и возвращается к func2 (1).
6. func2 (1) печатает 2, поскольку он увеличивает n и возвращается к func1 (3).
7. func1 (3) печатает 3 и возвращается к main().
8. main() возвращает и программа выходит.

Answer 2

Я нашел через обучение студентов, как рекурсия работает с локальными переменными является то, что самый простой способ понять это, если вы делаете именно то, что компьютер делает, - процесс шаг за шагом, и запишите то, что можно назвать и когда значения переменных изменить

, например:

main 
    func1(5) 
    n=5 
    printf 5 
    func2(5-2) 
     n=3 
     print 3 
     ++n 
     n=4 
     func1(4) 
     n=4 
     print 4 
     func2(4-2) 
      n=2 
      print 2 
      ++n 
      n=3 
      func1(3) 
      n=3 
      print 3 
      func2(3-2) 
       n=1 
       print 1 
       ++n 
       n=2 
       func1(2) 
       n=2 
       print 2 
       func2(2-2) 
        n=0 
        if n==0 => return 
       print 2 
       print 2 
      print 3 
      print 3 
     print 4 
     print 4 
    print 5 
    //done 

Вы также должны понимать, что в каждом вызове функции, изменения в «п» внутри функции не меняют ранее , откуда он был вызван.

вы можете увидеть это лучше, если вы представить себе компьютер делать что-то вроде этого: , где каждый вызов функции создает новый набор переменных на стеке, и когда функция возвращает, его переменные удаляются из стека.

stack: (empty) 

main 
    func1(5) ==> push n='5' on stack, then jump to func1() 
    stack is now { n=5 } 
    so n is 5 
    print 5 
    func2(5-2) ==> push 'n=3' on stack, then jump to func2() 
     stack is now { n=3 } , { n=5 } 
     so n is 3 
     print 3 
     ++n 
     stack is now { n=4 } , { n=5 } 
     func1(4) ==> push 'n=4' on stack then jump to func1() 
     stack is now { n=4} , { n=4 } , { n=5 } 
     so n is 4 
     print 4 
     func2(4-2) ==> push 'n=2' on stack then jump to func() 
      stack is now {n=2}, {n=4} , { n=4 } , { n=5 } 
      ++n 
      stack is now {n=3}, {n=4} , { n=4 } , { n=5 } 
      ...etc... 
      ..... 
      .... 
      stack is eventually {n=0} {n=2}, {n=2}, {n=2} ,{n=1} {n=3}, {n=3}, {n=4} , { n=4 } , { n=5 } 
      after func(2-2) is called 
      then: 
       if n==0 => return; 
      the return pops one item {n=0} off the stack, so 
      stack is then {n=2}, {n=2}, {n=2} ,{n=1} {n=3}, {n=3}, {n=4} , { n=4 } , { n=5 } 
      print 2 
      return (deletes {n=2}) 
      stack is then {n=2}, {n=2} ,{n=1} {n=3}, {n=3}, {n=4} , { n=4 } , { n=5 } 
      print 2 
     return (deletes {n=2}) 
     stack is then {n=2} ,{n=1} {n=3}, {n=3}, {n=4} , { n=4 } , { n=5 } 
     print 2 
     return (deletes {n=2}) 
    stack is then {n=1} {n=3}, {n=3}, {n=4} , { n=4 } , { n=5 } 
    print 1 
    return (deletes {n=1}) 
    stack is then {n=3}, {n=3}, {n=4} , { n=4 } , { n=5 } 
    print 3 

и так далее до тех пор, пока оно не закончится и не будет распечатано последнее «5».