Julie Johnson
Reputation: 23
How does the call macro enable mutual recursion between functions f and g in this Hanoi Tower implementation?
I’m trying to simulate the Tower of Hanoi problem using a manually managed stack to replace recursive calls. It's the code refactoring task(written in C),"Try to extend the non-recursive Tower of Hanoi to the case where the functions f and g call each other."I asked chatGPT,and this is the answer. The key part is the call macro, which pushes a new stack frame, and the ret macro, which pops a stack frame. The f and g functions are supposed to mimic mutual recursion (each calls the other indirectly via the call macro).
Why does the setup allow f and g to call each other?
When f executes call(n-1, from, via, to), it seems to call g (or itself?), but how does the program know to switch between f and g?
How does the pc mechanism ensure the correct sequence of operations (e.g., saving return values in c1/c2)?
Code:
#include <stdio.h>
#include <assert.h>
struct Frame {
int pc; // Program counter
int n; // Number of disks
char from, to, via; // Source, target, and auxiliary poles
int c1, c2; // Local variables: store return values of recursive calls
};
typedef struct Frame Frame;
#define MAX_FRAMES 64
Frame stk[MAX_FRAMES];
Frame *top = stk - 1; // Initial state of the stack
// The call macro simulates a function call by pushing a new frame onto the stack
#define call(...) ({ *(++top) = (Frame){.pc = 0, __VA_ARGS__}; })
// The ret macro simulates a function return by popping the top frame and returning a value
#define ret(val) ({ top--; retval = (val); })
// f function: Simulates the Tower of Hanoi move operation
int f(int n, char from, char to, char via);
// g function: Auxiliary operation, simulates a part of the Tower of Hanoi operation
int g(int n, char from, char to, char via);
int main() {
int n = 3; // Assume we have 3 disks
char from = 'A', to = 'B', via = 'C';
int step_count = f(n, from, to, via);
printf("\nHanoi(%d, %c, %c, %c) = %d\n", n, from, to, via, step_count);
return 0;
}
int f(int n, char from, char to, char via) {
int retval = 0;
call(n, from, to, via); // Initial call
while (1) {
Frame *f = top;
if (top < stk) break; // If the stack is empty, the recursion ends
int next_pc = f->pc + 1; // Get the next program counter value
int n = f->n, from = f->from, to = f->to, via = f->via;
switch (f->pc) {
case 0:
if (n == 1) {
printf("%c -> %c\n", from, to);
ret(1); // Base case, directly move the disk
}
break;
case 1:
call(n - 1, from, via, to); // Recursive call to g
break;
case 2:
f->c1 = retval; // Store the return value of g
break;
case 3:
call(1, from, to, via); // Move the largest disk
break;
case 4:
call(n - 1, via, to, from); // Recursive call to g again
break;
case 5:
f->c2 = retval; // Store the return value of g
break;
case 6:
ret(f->c1 + f->c2 + 1); // Return the total step count
break;
default:
assert(0); // If an unknown pc value appears, the program will assert failure
}
f->pc = next_pc; // Update the program counter
}
return retval;
}
// g function: In this function, we perform some operations
int g(int n, char from, char to, char via) {
int retval = 0;
call(n, from, to, via); // Initial call
while (1) {
Frame *f = top;
if (top < stk) break; // If the stack is empty, the recursion ends
int next_pc = f->pc + 1; // Get the next program counter value
int n = f->n, from = f->from, to = f->to, via = f->via;
switch (f->pc) {
case 0:
if (n == 1) {
printf("%c -> %c\n", from, to);
ret(1); // Base case, directly move the disk
}
break;
case 1:
call(n - 1, from, via, to); // Recursive call to f
break;
case 2:
f->c1 = retval; // Store the return value of f
break;
case 3:
call(1, from, to, via); // Move the largest disk
break;
case 4:
call(n - 1, via, to, from); // Recursive call to f again
break;
case 5:
f->c2 = retval; // Store the return value of f
break;
case 6:
ret(f->c1 + f->c2 + 1); // Return the total step count
break;
default:
assert(0); // If an unknown pc value appears, the program will assert failure
}
f->pc = next_pc; // Update the program counter
}
return retval;
}
What I tried: I've tried queried ChatGPT-4O for the entire process detail, but I can't make it clear how the the part of mutual recursion works in fact, could you expain it clearer?
What I expected:
I thought mutual recursion would require separate stack identifiers for f and g, but the code uses a single Frame struct. I can’t trace how the pc in switch(f->pc) routes execution to the correct function after each call.
Upvotes: 0
Views: 78
Answers (1)
chqrlie
Reputation: 145277
Function g is not used at all in the program. There is no actual recursion, nevertheless mutual recursion, the function f simulates recursion using a loop and a stack.
The recursive version can be be implemented using 2 mutually recursive functions, but in this non-recursive version using a stack structure, there is no actual recursion: the loop simulate the three recursive calls, the steps correspond to individual steps in the recursive version, f->c1 and f->c2 are updated with the return values of the first and third recursive call, just like the local variables in the call instances of the recursive version, mutual or not.
Note that this program is needlessly obfuscated and uses non-standard GNU extensions such as expression statements. Compiling with warnings enabled produces a lot of noise:
250301-hanoi.c:15:14: warning: the pointer decremented by 1 refers before the beginning of the array [-Warray-bounds-pointer-arithmetic]
Frame *top = stk - 1; // 栈的初始状态
^ ~
250301-hanoi.c:14:1: note: array 'stk' declared here
Frame stk[MAX_FRAMES];
^
250301-hanoi.c:39:5: warning: use of GNU statement expression extension from macro expansion
[-Wgnu-statement-expression-from-macro-expansion]
call(n, from, to, via); // 初始调用
^
250301-hanoi.c:18:20: note: expanded from macro 'call'
#define call(...) ({ *(++top) = (Frame){.pc = 0, __VA_ARGS__}; })
^
250301-hanoi.c:46:13: warning: declaration shadows a local variable [-Wshadow]
int n = f->n, from = f->from, to = f->to, via = f->via;
^
250301-hanoi.c:37:11: note: previous declaration is here
int f(int n, char from, char to, char via) {
^
250301-hanoi.c:46:23: warning: declaration shadows a local variable [-Wshadow]
int n = f->n, from = f->from, to = f->to, via = f->via;
^
250301-hanoi.c:37:19: note: previous declaration is here
int f(int n, char from, char to, char via) {
^
250301-hanoi.c:46:39: warning: declaration shadows a local variable [-Wshadow]
int n = f->n, from = f->from, to = f->to, via = f->via;
^
250301-hanoi.c:37:30: note: previous declaration is here
int f(int n, char from, char to, char via) {
^
250301-hanoi.c:46:51: warning: declaration shadows a local variable [-Wshadow]
int n = f->n, from = f->from, to = f->to, via = f->via;
^
250301-hanoi.c:37:39: note: previous declaration is here
int f(int n, char from, char to, char via) {
^
250301-hanoi.c:52:21: warning: use of GNU statement expression extension from macro expansion
[-Wgnu-statement-expression-from-macro-expansion]
ret(1); // 基本情况，直接移动盘子
^
250301-hanoi.c:21:19: note: expanded from macro 'ret'
#define ret(val) ({ top--; retval = (val); })
^
250301-hanoi.c:56:17: warning: use of GNU statement expression extension from macro expansion
[-Wgnu-statement-expression-from-macro-expansion]
call(n - 1, from, via, to); // 递归调用g
^
250301-hanoi.c:18:20: note: expanded from macro 'call'
#define call(...) ({ *(++top) = (Frame){.pc = 0, __VA_ARGS__}; })
^
250301-hanoi.c:56:40: warning: implicit conversion loses integer precision: 'int' to 'char' [-Wimplicit-int-conversion]
call(n - 1, from, via, to); // 递归调用g
~~~~~~~~~~~~~~~~~~~~~~~^~~
250301-hanoi.c:18:50: note: expanded from macro 'call'
#define call(...) ({ *(++top) = (Frame){.pc = 0, __VA_ARGS__}; })
~ ^~~~~~~~~~~
250301-hanoi.c:56:35: warning: implicit conversion loses integer precision: 'int' to 'char' [-Wimplicit-int-conversion]
call(n - 1, from, via, to); // 递归调用g
~~~~~~~~~~~~~~~~~~^~~~~~~~
250301-hanoi.c:18:50: note: expanded from macro 'call'
#define call(...) ({ *(++top) = (Frame){.pc = 0, __VA_ARGS__}; })
~ ^~~~~~~~~~~
250301-hanoi.c:56:29: warning: implicit conversion loses integer precision: 'int' to 'char' [-Wimplicit-int-conversion]
call(n - 1, from, via, to); // 递归调用g
~~~~~~~~~~~~^~~~~~~~~~~~~~
250301-hanoi.c:18:50: note: expanded from macro 'call'
#define call(...) ({ *(++top) = (Frame){.pc = 0, __VA_ARGS__}; })
~ ^~~~~~~~~~~
250301-hanoi.c:62:17: warning: use of GNU statement expression extension from macro expansion
[-Wgnu-statement-expression-from-macro-expansion]
call(1, from, to, via); // 移动最大的盘子
^
250301-hanoi.c:18:20: note: expanded from macro 'call'
#define call(...) ({ *(++top) = (Frame){.pc = 0, __VA_ARGS__}; })
^
250301-hanoi.c:62:35: warning: implicit conversion loses integer precision: 'int' to 'char' [-Wimplicit-int-conversion]
call(1, from, to, via); // 移动最大的盘子
~~~~~~~~~~~~~~~~~~^~~~
250301-hanoi.c:18:50: note: expanded from macro 'call'
#define call(...) ({ *(++top) = (Frame){.pc = 0, __VA_ARGS__}; })
~ ^~~~~~~~~~~
250301-hanoi.c:62:31: warning: implicit conversion loses integer precision: 'int' to 'char' [-Wimplicit-int-conversion]
call(1, from, to, via); // 移动最大的盘子
~~~~~~~~~~~~~~^~~~~~~~
250301-hanoi.c:18:50: note: expanded from macro 'call'
#define call(...) ({ *(++top) = (Frame){.pc = 0, __VA_ARGS__}; })
~ ^~~~~~~~~~~
250301-hanoi.c:62:25: warning: implicit conversion loses integer precision: 'int' to 'char' [-Wimplicit-int-conversion]
call(1, from, to, via); // 移动最大的盘子
~~~~~~~~^~~~~~~~~~~~~~
250301-hanoi.c:18:50: note: expanded from macro 'call'
#define call(...) ({ *(++top) = (Frame){.pc = 0, __VA_ARGS__}; })
~ ^~~~~~~~~~~
250301-hanoi.c:65:17: warning: use of GNU statement expression extension from macro expansion
[-Wgnu-statement-expression-from-macro-expansion]
call(n - 1, via, to, from); // 再次递归调用g
^
250301-hanoi.c:18:20: note: expanded from macro 'call'
#define call(...) ({ *(++top) = (Frame){.pc = 0, __VA_ARGS__}; })
^
250301-hanoi.c:65:38: warning: implicit conversion loses integer precision: 'int' to 'char' [-Wimplicit-int-conversion]
call(n - 1, via, to, from); // 再次递归调用g
~~~~~~~~~~~~~~~~~~~~~^~~~~
250301-hanoi.c:18:50: note: expanded from macro 'call'
#define call(...) ({ *(++top) = (Frame){.pc = 0, __VA_ARGS__}; })
~ ^~~~~~~~~~~
250301-hanoi.c:65:34: warning: implicit conversion loses integer precision: 'int' to 'char' [-Wimplicit-int-conversion]
call(n - 1, via, to, from); // 再次递归调用g
~~~~~~~~~~~~~~~~~^~~~~~~~~
250301-hanoi.c:18:50: note: expanded from macro 'call'
#define call(...) ({ *(++top) = (Frame){.pc = 0, __VA_ARGS__}; })
~ ^~~~~~~~~~~
250301-hanoi.c:65:29: warning: implicit conversion loses integer precision: 'int' to 'char' [-Wimplicit-int-conversion]
call(n - 1, via, to, from); // 再次递归调用g
~~~~~~~~~~~~^~~~~~~~~~~~~~
250301-hanoi.c:18:50: note: expanded from macro 'call'
#define call(...) ({ *(++top) = (Frame){.pc = 0, __VA_ARGS__}; })
~ ^~~~~~~~~~~
250301-hanoi.c:71:17: warning: use of GNU statement expression extension from macro expansion
[-Wgnu-statement-expression-from-macro-expansion]
ret(f->c1 + f->c2 + 1); // 返回总步数
^
250301-hanoi.c:21:19: note: expanded from macro 'ret'
#define ret(val) ({ top--; retval = (val); })
^
20 warnings generated.
The GNU extensions can be replaced with portable do/while(0) constructions, and the other warnings can be solved easily. Note that retval can be incremented directly in step 0 so there is no need for c1 and c2 and the intermediary steps.
Here is a modified, simplified and translated version:
#include <stdio.h>
#include <assert.h>
// f function: Simulate the Tower of Hanoi move operation
int f(int n, char from, char to, char via);
int main(void) {
int n = 3; // Assume we have 3 disks
char from = 'A', to = 'B', via = 'C';
int step_count = f(n, from, to, via);
printf("\nHanoi(%d, %c, %c, %c) = %d\n", n, from, to, via, step_count);
return 0;
}
int f(int n, char from, char to, char via) {
typedef struct Frame {
int pc; // Program counter
int n; // Number of disks
char from, to, via; // Source, target, and auxiliary rods
} Frame;
// The 'call' macro is used to simulate a function call, pushing a new stack frame onto the stack
#define call(...) do { *(++top) = (Frame){ 0, __VA_ARGS__ }; } while(0)
// The 'ret' macro is used to simulate a function return, popping the top stack frame
#define ret() do { top--; } while(0)
#define MAX_FRAMES 64 // enough for moving 64 disks, but be patient forever
Frame stk[MAX_FRAMES + 1];
Frame *top = stk; // Initial state of the stack
int retval = 0;
call(n, from, to, via); // Initial call
while (top > stk) {
Frame *f = top;
n = f->n;
from = f->from;
to = f->to;
via = f->via;
switch (f->pc++) {
case 0:
if (n == 1) {
printf("%c -> %c\n", from, to);
retval += 1; // Update the counter directly
ret(); // Return without recursing
}
break;
case 1:
call(n - 1, from, via, to); // Recursive call to move n-1 disks
break;
case 2:
call(1, from, to, via); // Move the largest disk
break;
case 3:
call(n - 1, via, to, from); // Recursive call to move n-1 disks again
break;
case 4:
ret(); // Return from recursive call
break;
default:
assert(0); // If an unknown pc value appears, the program will assert failure
}
}
return retval;
}
Upvotes: 2