// In this log we'll see how recursion works in C and allows a function 
//   to call itself from its own body without confusion as to where the
//   current and precious arguments and variables are stored and when
//   they are accessed.

// We are going to use recursion to compute the factorial function (written "n!")
//  0! is defined as 1, n! is defined as 1*2*..*(n-1)*n, the product of all integers from 1 to n  
//  Recall that 
//              1! = 1
//              2! = 2
//              3! = 6
//              4! = 24
//              5! = 120
//              6! = 720  etc.

// We could do it in a loop, but let's not. Instead, let's make use of the inductive
//   definition: n! = n * (n-1)! for n>1 , 0! = 1

// As we'll see later in the course, inductively defined functions and data structures
//   are much easier to write the least amount of code for, and to prove correct.
// 
// Essentially, we just need to get the base case right, and then program a small number
//   of operations that make whatever we need out of a previously prepared object, rather
//   than planning the entire loop. This saves programming effort and analysis/proof effort
//   ever more so.

[sergey@thepond ~]$ cat fact5.c
#include <stdio.h>

/* a very naive recursive factorial */
unsigned int fact(unsigned int n)
{
  // printf("%p %d\n", &n, n);  <<-- uncomment this line and see the addresses of n
     if( n == 0 )               // <-- base case of the recursive definition  
          return 1;
     return n * fact(n-1);      // <-- inductive definition step
}

int main()
{
     printf("%d\n", fact(7));
     return 0;
}

// But, how can a function call itself and not get confused where its arguments and variables are?
//   Read on :)

[sergey@thepond ~]$ gcc -S -fno-asynchronous-unwind-tables fact5.c

[sergey@thepond ~]$ cat fact5.s
	.file	"fact5.c"
	.text
	.globl	fact
	.type	fact, @function
fact:
	pushq	%rbp
	movq	%rsp, %rbp
	subq	$16, %rsp       // make a stack frame 
	movl	%edi, -4(%rbp)  // the argument "n" will be saved in the first 4 bytes of the frame
	cmpl	$0, -4(%rbp)    // if "n" a zero? 
	jne	.L2             // if not, jump to L2
	movl	$1, %eax        // if yes (prior jump not taken), the return value is 1 
	jmp	.L3             //  and we jump to the exit post-amble
.L2:
	movl	-4(%rbp), %eax  // inductive step. Get "n"
	subl	$1, %eax        //   make n-1 
	movl	%eax, %edi      //   as the argument to the next call to fact()
	call	fact
	imull	-4(%rbp), %eax  // At this point, EAX will contain the result of fact(n-1).
	                        //   So multiply it by the value of "n" saved in _this_ frame.
				//   The multiplication result ends up in EAX
.L3:
	leave                   // Standard post-amble: mov %rbp, %rsp
	ret                     //  pop 8 bytes off the stack, interpret as an address, jump there
	.size	fact, .-fact
	.section	.rodata
.LC0:
	.string	"%d\n"
	.text
	.globl	main
	.type	main, @function
main:
	pushq	%rbp
	movq	%rsp, %rbp
	movl	$7, %edi
	call	fact
	movl	%eax, %edx        // result of fact() saved to EDX
	leaq	.LC0(%rip), %rax  // global, format string for printf()
	movl	%edx, %esi        //   result of fact() becomes the second argument to printf()
	movq	%rax, %rdi        // the constant format string is the first argument to printf()
	movl	$0, %eax          // This is a weird special case for printf: no floating point arguments 
	call	printf@PLT
	movl	$0, %eax
	popq	%rbp              // Note: not "leave", but equivalent for the upcoming RET
	ret
	.size	main, .-main
	.ident	"GCC: (GNU) 15.2.1 20250813"
	.section	.note.GNU-stack,"",@progbits

[sergey@thepond ~]$ 

// Now build it and run it

[sergey@thepond ~]$ gcc -o fact5 fact5.c

[sergey@thepond ~]$ ./fact5
5040

[sergey@thepond ~]$ gdb ./fact5
GNU gdb (GDB) 16.3
Copyright (C) 2024 Free Software Foundation, Inc.
License GPLv3+: GNU GPL version 3 or later <http://gnu.org/licenses/gpl.html>
This is free software: you are free to change and redistribute it.
There is NO WARRANTY, to the extent permitted by law.
Type "show copying" and "show warranty" for details.
This GDB was configured as "x86_64-pc-linux-gnu".
Type "show configuration" for configuration details.
For bug reporting instructions, please see:
<https://www.gnu.org/software/gdb/bugs/>.
Find the GDB manual and other documentation resources online at:
    <http://www.gnu.org/software/gdb/documentation/>.

For help, type "help".
Type "apropos word" to search for commands related to "word"...
Reading symbols from ./fact5...

This GDB supports auto-downloading debuginfo from the following URLs:
  <https://debuginfod.archlinux.org>
Enable debuginfod for this session? (y or [n]) 
Debuginfod has been disabled.
To make this setting permanent, add 'set debuginfod enabled off' to .gdbinit.
(No debugging symbols found in ./fact5)

(gdb) disas main
Dump of assembler code for function main:
   0x0000000000001164 <+0>:	push   %rbp
   0x0000000000001165 <+1>:	mov    %rsp,%rbp
   0x0000000000001168 <+4>:	mov    $0x7,%edi
   0x000000000000116d <+9>:	call   0x1139 <fact>
   0x0000000000001172 <+14>:	mov    %eax,%edx
   0x0000000000001174 <+16>:	lea    0xe89(%rip),%rax        # 0x2004  // address of format string
   0x000000000000117b <+23>:	mov    %edx,%esi
   0x000000000000117d <+25>:	mov    %rax,%rdi
   0x0000000000001180 <+28>:	mov    $0x0,%eax
   0x0000000000001185 <+33>:	call   0x1030 <printf@plt>
   0x000000000000118a <+38>:	mov    $0x0,%eax
   0x000000000000118f <+43>:	pop    %rbp
   0x0000000000001190 <+44>:	ret
End of assembler dump.

(gdb) disas fact
Dump of assembler code for function fact:
   0x0000000000001139 <+0>:	push   %rbp
   0x000000000000113a <+1>:	mov    %rsp,%rbp
   0x000000000000113d <+4>:	sub    $0x10,%rsp
   0x0000000000001141 <+8>:	mov    %edi,-0x4(%rbp)
   0x0000000000001144 <+11>:	cmpl   $0x0,-0x4(%rbp)
   0x0000000000001148 <+15>:	jne    0x1151 <fact+24>
   0x000000000000114a <+17>:	mov    $0x1,%eax
   0x000000000000114f <+22>:	jmp    0x1162 <fact+41>
   0x0000000000001151 <+24>:	mov    -0x4(%rbp),%eax
   0x0000000000001154 <+27>:	sub    $0x1,%eax
   0x0000000000001157 <+30>:	mov    %eax,%edi
   0x0000000000001159 <+32>:	call   0x1139 <fact>
   0x000000000000115e <+37>:	imul   -0x4(%rbp),%eax
   0x0000000000001162 <+41>:	leave
   0x0000000000001163 <+42>:	ret
End of assembler dump.

(gdb) b main
Breakpoint 1 at 0x1168

// Let's run it to get it loaded into memory and get real addresses rather than offsets as above.
//  With real addresses, we can then set breakpoints on individual instructions

(gdb) r
Starting program: /home/sergey/fact5 
[Thread debugging using libthread_db enabled]
Using host libthread_db library "/usr/lib/libthread_db.so.1".

Breakpoint 1, 0x0000555555555168 in main ()

(gdb) disas main
Dump of assembler code for function main:
   0x0000555555555164 <+0>:	push   %rbp
   0x0000555555555165 <+1>:	mov    %rsp,%rbp
=> 0x0000555555555168 <+4>:	mov    $0x7,%edi    // <-- first and only argument passed to fact()
   0x000055555555516d <+9>:	call   0x555555555139 <fact>
   0x0000555555555172 <+14>:	mov    %eax,%edx
   0x0000555555555174 <+16>:	lea    0xe89(%rip),%rax        # 0x555555556004
   0x000055555555517b <+23>:	mov    %edx,%esi
   0x000055555555517d <+25>:	mov    %rax,%rdi
   0x0000555555555180 <+28>:	mov    $0x0,%eax
   0x0000555555555185 <+33>:	call   0x555555555030 <printf@plt>
   0x000055555555518a <+38>:	mov    $0x0,%eax
   0x000055555555518f <+43>:	pop    %rbp
   0x0000555555555190 <+44>:	ret
End of assembler dump.

// We are about to execute store of 7 to EDI. What's there now?

(gdb) i r edi 
edi            0x1                 1

// Why? This is the first argument to main() at this time. See the interlude below for what
//  it means. But now we execute our pending instruction:

(gdb) si
0x000055555555516d in main ()

(gdb) i r edi 
edi            0x7                 7     // <-- and there's our 7 there now

// We are about to enter CALL:

(gdb) disas main
Dump of assembler code for function main:
   0x0000555555555164 <+0>:	push   %rbp
   0x0000555555555165 <+1>:	mov    %rsp,%rbp
   0x0000555555555168 <+4>:	mov    $0x7,%edi
=> 0x000055555555516d <+9>:	call   0x555555555139 <fact>
   0x0000555555555172 <+14>:	mov    %eax,%edx              // <-- we return here after CALL,
                                                              //      and save the return value to EDX
   0x0000555555555174 <+16>:	lea    0xe89(%rip),%rax        # 0x555555556004
   0x000055555555517b <+23>:	mov    %edx,%esi
   0x000055555555517d <+25>:	mov    %rax,%rdi
   0x0000555555555180 <+28>:	mov    $0x0,%eax
   0x0000555555555185 <+33>:	call   0x555555555030 <printf@plt>
   0x000055555555518a <+38>:	mov    $0x0,%eax
   0x000055555555518f <+43>:	pop    %rbp
   0x0000555555555190 <+44>:	ret
End of assembler dump.

(gdb) i r rip rsp 
rip            0x55555555516d      0x55555555516d <main+9>
rsp            0x7fffffffeac0      0x7fffffffeac0

// and now step:

(gdb) si
0x0000555555555139 in fact ()

// We jumped to the preamble of fact(). RSP moved by 8 bytes. What was saved in those 8 bytes?

(gdb) i r rip rsp 
rip            0x555555555139      0x555555555139 <fact>
rsp            0x7fffffffeab8      0x7fffffffeab8

// Of course, the address of the next instruction after "call fact", see above: 

(gdb) x/xg 0x7fffffffeab8
0x7fffffffeab8:	0x0000555555555172   // "x/xg $rsp"   would produce the same result

// OK, we are now entering fact()

(gdb) disas fact
Dump of assembler code for function fact:
=> 0x0000555555555139 <+0>:	push   %rbp
   0x000055555555513a <+1>:	mov    %rsp,%rbp
   0x000055555555513d <+4>:	sub    $0x10,%rsp
   0x0000555555555141 <+8>:	mov    %edi,-0x4(%rbp)
   0x0000555555555144 <+11>:	cmpl   $0x0,-0x4(%rbp)
   0x0000555555555148 <+15>:	jne    0x555555555151 <fact+24>
   0x000055555555514a <+17>:	mov    $0x1,%eax
   0x000055555555514f <+22>:	jmp    0x555555555162 <fact+41>
   0x0000555555555151 <+24>:	mov    -0x4(%rbp),%eax
   0x0000555555555154 <+27>:	sub    $0x1,%eax
   0x0000555555555157 <+30>:	mov    %eax,%edi
   0x0000555555555159 <+32>:	call   0x555555555139 <fact>
   0x000055555555515e <+37>:	imul   -0x4(%rbp),%eax
   0x0000555555555162 <+41>:	leave
   0x0000555555555163 <+42>:	ret
End of assembler dump.

(gdb) si
0x000055555555513a in fact ()

// RSP moved by another 8 bytes:

(gdb) i r rsp 
rsp            0x7fffffffeab0      0x7fffffffeab0

// .. to save main()'s base pointer in RBP:

(gdb) x/xg $rsp
0x7fffffffeab0:	0x00007fffffffeac0

(gdb) i r rbp
rbp            0x7fffffffeac0      0x7fffffffeac0

(gdb) si
0x000055555555513d in fact ()

// .. and now RSP gets copied to RBP and becomes the base pointer of the new frame:

(gdb) i r rsp rbp
rsp            0x7fffffffeab0      0x7fffffffeab0
rbp            0x7fffffffeab0      0x7fffffffeab0

(gdb) disas fact
Dump of assembler code for function fact:
   0x0000555555555139 <+0>:	push   %rbp
   0x000055555555513a <+1>:	mov    %rsp,%rbp
=> 0x000055555555513d <+4>:	sub    $0x10,%rsp
   0x0000555555555141 <+8>:	mov    %edi,-0x4(%rbp)
   0x0000555555555144 <+11>:	cmpl   $0x0,-0x4(%rbp)
   0x0000555555555148 <+15>:	jne    0x555555555151 <fact+24>
   0x000055555555514a <+17>:	mov    $0x1,%eax
   0x000055555555514f <+22>:	jmp    0x555555555162 <fact+41>
   0x0000555555555151 <+24>:	mov    -0x4(%rbp),%eax
   0x0000555555555154 <+27>:	sub    $0x1,%eax
   0x0000555555555157 <+30>:	mov    %eax,%edi
   0x0000555555555159 <+32>:	call   0x555555555139 <fact>  // <<-- let's break here
   0x000055555555515e <+37>:	imul   -0x4(%rbp),%eax
   0x0000555555555162 <+41>:	leave
   0x0000555555555163 <+42>:	ret
End of assembler dump.

// Set the breakpoint at the recursive call:

(gdb) b *0x0000555555555159
Breakpoint 2 at 0x555555555159

(gdb) c
Continuing.

Breakpoint 2, 0x0000555555555159 in fact ()

(gdb) disas fact
Dump of assembler code for function fact:
   0x0000555555555139 <+0>:	push   %rbp
   0x000055555555513a <+1>:	mov    %rsp,%rbp
   0x000055555555513d <+4>:	sub    $0x10,%rsp
   0x0000555555555141 <+8>:	mov    %edi,-0x4(%rbp)
   0x0000555555555144 <+11>:	cmpl   $0x0,-0x4(%rbp)
   0x0000555555555148 <+15>:	jne    0x555555555151 <fact+24>
   0x000055555555514a <+17>:	mov    $0x1,%eax
   0x000055555555514f <+22>:	jmp    0x555555555162 <fact+41>
   0x0000555555555151 <+24>:	mov    -0x4(%rbp),%eax
   0x0000555555555154 <+27>:	sub    $0x1,%eax
   0x0000555555555157 <+30>:	mov    %eax,%edi
=> 0x0000555555555159 <+32>:	call   0x555555555139 <fact>
   0x000055555555515e <+37>:	imul   -0x4(%rbp),%eax
   0x0000555555555162 <+41>:	leave
   0x0000555555555163 <+42>:	ret
End of assembler dump.

(gdb) x/4xg $rsp
0x7fffffffeaa0:	0x0000000000000000	0x0000000700000000   // <-- saved argument (an int, 4 bytes)
                                        ^^^^^^^^^^
0x7fffffffeab0:	0x00007fffffffeac0	0x0000555555555172   // <-- saved RBP, return address in main()
                ^^^^^^^^^^^^^^^^^^      ^^^^^^^^^^^^^^^^^^

// Note that the zeros above are accidental, it's just what was in the memory. Frames are
//   not zeroed out on creation, and contain "holes" that are neither read nor written.

// Now we execute the CALL:

(gdb) si
0x0000555555555139 in fact ()

// Return address is now saved to the top of the stack, RSP shifts by 8 bytes:

(gdb) x/12xg $rsp
0x7fffffffea98:	0x000055555555515e	0x0000000000000000
                ^^^^^^^^^^^^^^^^^^
0x7fffffffeaa8:	0x0000000700000000	0x00007fffffffeac0
0x7fffffffeab8:	0x0000555555555172	0x00007fffffffeb60
0x7fffffffeac8:	0x00007ffff7c27675	0x00007ffff7fc2000
0x7fffffffead8:	0x00007fffffffebe8	0x00000001ffffeb20
0x7fffffffeae8:	0x0000555555555164	0x0000000000000000

// And we are now back at the entry point of fact():

(gdb) i r rip
rip            0x555555555139      0x555555555139 <fact>

// We'll let the code run and hit the breakpoint several times. More frames will be created:

(gdb) c
Continuing.

Breakpoint 2, 0x0000555555555159 in fact ()
(gdb) c
Continuing.

Breakpoint 2, 0x0000555555555159 in fact ()
(gdb) c
Continuing.

Breakpoint 2, 0x0000555555555159 in fact ()

// Observe the recursive stack frames, each with a saved value of "n" and the same return address
//  into fact() right after the recursive call to fact():

(gdb) x/16xg $rsp
0x7fffffffea40:	0xffffffffffffffff	0x00000004004a0000
                                        ^^^^^^^^^^          // saved argument
0x7fffffffea50:	0x00007fffffffea70	0x000055555555515e  // <<-- return address in fact()
0x7fffffffea60:	0x0000000000940000	0x00000005ffffea98
                                        ^^^^^^^^^^
0x7fffffffea70:	0x00007fffffffea90	0x000055555555515e  // <<-- ditto
0x7fffffffea80:	0x0000000000000000	0x0000000600000000
                                        ^^^^^^^^^^
0x7fffffffea90:	0x00007fffffffeab0	0x000055555555515e  // <-- ditto
0x7fffffffeaa0:	0x0000000000000000	0x0000000700000000
                                        ^^^^^^^^^^ 
0x7fffffffeab0:	0x00007fffffffeac0	0x0000555555555172  // <<-- return address in main()

// You might wonder, why does an "unsigned int n" show that way on the stack when viewed
//  as 8-byte integers. The answer is in the little-endian representation:

(gdb) x/16xb $rsp
0x7fffffffea40:	0xff	0xff	0xff	0xff	0xff	0xff	0xff	0xff
0x7fffffffea48:	0x00	0x00	0x4a	0x00	0x04	0x00	0x00	0x00
                ^^^^^^^^^^^^^^^^^^^^^^^^^^^^    ^^^^^^^^^^^^^^^^^^^^^^^^^^^^
		       leftover memory              little-endian 4 
                         (just junk)                  (least significant byte first)

(gdb) disas fact
Dump of assembler code for function fact:
   0x0000555555555139 <+0>:	push   %rbp
   0x000055555555513a <+1>:	mov    %rsp,%rbp
   0x000055555555513d <+4>:	sub    $0x10,%rsp
   0x0000555555555141 <+8>:	mov    %edi,-0x4(%rbp)
   0x0000555555555144 <+11>:	cmpl   $0x0,-0x4(%rbp)
   0x0000555555555148 <+15>:	jne    0x555555555151 <fact+24>
   0x000055555555514a <+17>:	mov    $0x1,%eax
   0x000055555555514f <+22>:	jmp    0x555555555162 <fact+41>
   0x0000555555555151 <+24>:	mov    -0x4(%rbp),%eax
   0x0000555555555154 <+27>:	sub    $0x1,%eax
   0x0000555555555157 <+30>:	mov    %eax,%edi
=> 0x0000555555555159 <+32>:	call   0x555555555139 <fact>
   0x000055555555515e <+37>:	imul   -0x4(%rbp),%eax
   0x0000555555555162 <+41>:	leave
   0x0000555555555163 <+42>:	ret
End of assembler dump.

// let's see all frames:

(gdb) c
Continuing.

Breakpoint 2, 0x0000555555555159 in fact ()

(gdb) c
Continuing.

Breakpoint 2, 0x0000555555555159 in fact ()

(gdb) c
Continuing.

Breakpoint 2, 0x0000555555555159 in fact ()
(gdb) x/28xg $rsp
0x7fffffffe9e0:	0xd18f032900000002	0x0000000100000010  // frame with n=1 saved
                                        ^^^^^^^^^^
0x7fffffffe9f0:	0x00007fffffffea10	0x000055555555515e
0x7fffffffea00:	0xffffffffffffffff	0x0000000200100000  // frame with n=2 saved
0x7fffffffea10:	0x00007fffffffea30	0x000055555555515e
0x7fffffffea20:	0x0000000000000008	0x0000000300008000  // frame with n=3 saved 
0x7fffffffea30:	0x00007fffffffea50	0x000055555555515e
0x7fffffffea40:	0xffffffffffffffff	0x00000004004a0000  // frame with n=4 saved
0x7fffffffea50:	0x00007fffffffea70	0x000055555555515e
0x7fffffffea60:	0x0000000000940000	0x00000005ffffea98  // frame with n=5 saved 
0x7fffffffea70:	0x00007fffffffea90	0x000055555555515e
0x7fffffffea80:	0x0000000000000000	0x0000000600000000  // frame with n=6 saved
0x7fffffffea90:	0x00007fffffffeab0	0x000055555555515e
0x7fffffffeaa0:	0x0000000000000000	0x0000000700000000  // frame with n=7 saved
0x7fffffffeab0:	0x00007fffffffeac0	0x0000555555555172  // frame in main() to return to

// Note that the saved RBP values in the first column jump by 0x20 each time.
//   This is because fact() code uses 0x10 for each stack frame _and_ there are two additional
//   instructions that each push 8 bytes, "push %rbp" and "call func". 16 + 8 + 8 = 32 == 0x20

// Also note that they are interspersed with "junk" like 0xffffffffffffffff 0x0000000000000008
//   0x0000000000940000 0x0000000000000000 etc. These are "holes" in fact()'s frame, neither
//   read nor written. They exist because the compilers prefers stack frames to be aligned
//   at 16 byte boundaries.
// However, these stack frames could be just 8 bytes long or even 4 bytes.
//   You can check this by editing fact5.s to replace "subq $16, %rsp" at the top of fact()
//   with "subq $8, %rsp" or "subq $4, %rsp" and then rebuild the binary with
//   "gcc -o fact5 fact5.s". It works. You can even make it 5 or 7, although reading the stack
//   will be a bit weird.


// .. and the last iteration:

(gdb) disas fact
Dump of assembler code for function fact:
   0x0000555555555139 <+0>:	push   %rbp
   0x000055555555513a <+1>:	mov    %rsp,%rbp
   0x000055555555513d <+4>:	sub    $0x10,%rsp
   0x0000555555555141 <+8>:	mov    %edi,-0x4(%rbp)
   0x0000555555555144 <+11>:	cmpl   $0x0,-0x4(%rbp)
   0x0000555555555148 <+15>:	jne    0x555555555151 <fact+24>
   0x000055555555514a <+17>:	mov    $0x1,%eax
   0x000055555555514f <+22>:	jmp    0x555555555162 <fact+41>
   0x0000555555555151 <+24>:	mov    -0x4(%rbp),%eax
   0x0000555555555154 <+27>:	sub    $0x1,%eax
   0x0000555555555157 <+30>:	mov    %eax,%edi
=> 0x0000555555555159 <+32>:	call   0x555555555139 <fact>
   0x000055555555515e <+37>:	imul   -0x4(%rbp),%eax
   0x0000555555555162 <+41>:	leave
   0x0000555555555163 <+42>:	ret
End of assembler dump.

(gdb) si
0x0000555555555139 in fact ()

(gdb) i r edi
edi            0x0                 0

(gdb) si 
0x000055555555513a in fact ()

(gdb) disas fact
Dump of assembler code for function fact:
   0x0000555555555139 <+0>:	push   %rbp
=> 0x000055555555513a <+1>:	mov    %rsp,%rbp
   0x000055555555513d <+4>:	sub    $0x10,%rsp
   0x0000555555555141 <+8>:	mov    %edi,-0x4(%rbp)
   0x0000555555555144 <+11>:	cmpl   $0x0,-0x4(%rbp)
   0x0000555555555148 <+15>:	jne    0x555555555151 <fact+24>
   0x000055555555514a <+17>:	mov    $0x1,%eax
   0x000055555555514f <+22>:	jmp    0x555555555162 <fact+41>
   0x0000555555555151 <+24>:	mov    -0x4(%rbp),%eax
   0x0000555555555154 <+27>:	sub    $0x1,%eax
   0x0000555555555157 <+30>:	mov    %eax,%edi
   0x0000555555555159 <+32>:	call   0x555555555139 <fact>
   0x000055555555515e <+37>:	imul   -0x4(%rbp),%eax
   0x0000555555555162 <+41>:	leave
   0x0000555555555163 <+42>:	ret
End of assembler dump.

(gdb) si
0x000055555555513d in fact ()

(gdb) si
0x0000555555555141 in fact ()

(gdb) disas fact
Dump of assembler code for function fact:
   0x0000555555555139 <+0>:	push   %rbp
   0x000055555555513a <+1>:	mov    %rsp,%rbp
   0x000055555555513d <+4>:	sub    $0x10,%rsp
=> 0x0000555555555141 <+8>:	mov    %edi,-0x4(%rbp)
   0x0000555555555144 <+11>:	cmpl   $0x0,-0x4(%rbp)
   0x0000555555555148 <+15>:	jne    0x555555555151 <fact+24>
   0x000055555555514a <+17>:	mov    $0x1,%eax
   0x000055555555514f <+22>:	jmp    0x555555555162 <fact+41>
   0x0000555555555151 <+24>:	mov    -0x4(%rbp),%eax
   0x0000555555555154 <+27>:	sub    $0x1,%eax
   0x0000555555555157 <+30>:	mov    %eax,%edi
   0x0000555555555159 <+32>:	call   0x555555555139 <fact>
   0x000055555555515e <+37>:	imul   -0x4(%rbp),%eax
   0x0000555555555162 <+41>:	leave
   0x0000555555555163 <+42>:	ret
End of assembler dump.

(gdb) c
Continuing.
5040                           // result, 7! = 5040

[Inferior 1 (process 406203) exited normally]

// Oops, I let the process exit, no more memory or register state. Off-by one, as humans do :)

(gdb) i r rsp
The program has no registers now.

// Nothing for it, I just need another breakpoint near the end of the program. My prior
//  breakpoints are still active:

(gdb) info bre
Num     Type           Disp Enb Address            What
1       breakpoint     keep y   0x0000555555555168 <main+4>
	breakpoint already hit 1 time
2       breakpoint     keep y   0x0000555555555159 <fact+32>
	breakpoint already hit 7 times        // <-- Note GDB's statistics per breakpoint

// Now adding an extra breakpoint so that we can examine the full stack after fact(7) returns to main()

(gdb) b *0x0000555555555172
Breakpoint 3 at 0x555555555172

(gdb) r
Starting program: /home/sergey/fact5 
[Thread debugging using libthread_db enabled]
Using host libthread_db library "/usr/lib/libthread_db.so.1".

Breakpoint 1, 0x0000555555555168 in main ()
(gdb) c
Continuing.

Breakpoint 2, 0x0000555555555159 in fact ()
(gdb) c
Continuing.

Breakpoint 2, 0x0000555555555159 in fact ()
(gdb) c
Continuing.

Breakpoint 2, 0x0000555555555159 in fact ()
(gdb) c
Continuing.

Breakpoint 2, 0x0000555555555159 in fact ()
(gdb) c
Continuing.

Breakpoint 2, 0x0000555555555159 in fact ()
(gdb) c
Continuing.

Breakpoint 2, 0x0000555555555159 in fact ()
(gdb) c
Continuing.

Breakpoint 2, 0x0000555555555159 in fact ()

(gdb) i r rsp
rsp            0x7fffffffe9e0      0x7fffffffe9e0

// There we have it, the stack with all frames:

(gdb) x/32xg $rsp
0x7fffffffe9e0:	0xd18f032900000002	0x0000000100000010  // n = 1
                                        ^^^^^^^^^^
0x7fffffffe9f0:	0x00007fffffffea10	0x000055555555515e
0x7fffffffea00:	0xffffffffffffffff	0x0000000200100000
0x7fffffffea10:	0x00007fffffffea30	0x000055555555515e
0x7fffffffea20:	0x0000000000000008	0x0000000300008000
0x7fffffffea30:	0x00007fffffffea50	0x000055555555515e
0x7fffffffea40:	0xffffffffffffffff	0x00000004004a0000
0x7fffffffea50:	0x00007fffffffea70	0x000055555555515e
0x7fffffffea60:	0x0000000000940000	0x00000005ffffea98
0x7fffffffea70:	0x00007fffffffea90	0x000055555555515e
0x7fffffffea80:	0x0000000000000000	0x0000000600000000
0x7fffffffea90:	0x00007fffffffeab0	0x000055555555515e
0x7fffffffeaa0:	0x0000000000000000	0x0000000700000000
0x7fffffffeab0:	0x00007fffffffeac0	0x0000555555555172
0x7fffffffeac0:	0x00007fffffffeb60	0x00007ffff7c27675
0x7fffffffead0:	0x00007ffff7fc2000	0x00007fffffffebe8

(gdb) c
Continuing.

Breakpoint 3, 0x0000555555555172 in main ()
(gdb) disas main
Dump of assembler code for function main:
   0x0000555555555164 <+0>:	push   %rbp
   0x0000555555555165 <+1>:	mov    %rsp,%rbp
   0x0000555555555168 <+4>:	mov    $0x7,%edi
   0x000055555555516d <+9>:	call   0x555555555139 <fact>
=> 0x0000555555555172 <+14>:	mov    %eax,%edx
   0x0000555555555174 <+16>:	lea    0xe89(%rip),%rax        # 0x555555556004
   0x000055555555517b <+23>:	mov    %edx,%esi
   0x000055555555517d <+25>:	mov    %rax,%rdi
   0x0000555555555180 <+28>:	mov    $0x0,%eax
   0x0000555555555185 <+33>:	call   0x555555555030 <printf@plt>
   0x000055555555518a <+38>:	mov    $0x0,%eax
   0x000055555555518f <+43>:	pop    %rbp
   0x0000555555555190 <+44>:	ret
End of assembler dump.

// And we are back to main()'s stack frame:

(gdb) i r rsp
rsp            0x7fffffffeac0      0x7fffffffeac0



// Let's see what C globals vs globals look like:

[sergey@thepond ~]$ cat l-vs-g.c 
#include <stdio.h>

int x = 1;
int y = 200;

void g();

int main()
{
    int x  = 100;
    printf( "f: x=%d y=%d\n", x, y);
    
    g();
    return 0;
}

void g()
{
    printf( "g: x=%d y=%d\n",   x,  y);
    printf( "&x=%p &y=%p\n", &x, &y);
}

[sergey@thepond ~]$ gcc -o l-vs-g l-vs-g.c 

[sergey@thepond ~]$ ./l-vs-g
f: x=100 y=200
g: x=1 y=200
&x=0x5b381b461018 &y=0x5b381b46101c

[sergey@thepond ~]$ gdb ./l-vs-g
GNU gdb (GDB) 16.3
Copyright (C) 2024 Free Software Foundation, Inc.
License GPLv3+: GNU GPL version 3 or later <http://gnu.org/licenses/gpl.html>
This is free software: you are free to change and redistribute it.
There is NO WARRANTY, to the extent permitted by law.
Type "show copying" and "show warranty" for details.
This GDB was configured as "x86_64-pc-linux-gnu".
Type "show configuration" for configuration details.
For bug reporting instructions, please see:
<https://www.gnu.org/software/gdb/bugs/>.
Find the GDB manual and other documentation resources online at:
    <http://www.gnu.org/software/gdb/documentation/>.

For help, type "help".
Type "apropos word" to search for commands related to "word"...
Reading symbols from ./l-vs-g...

This GDB supports auto-downloading debuginfo from the following URLs:
  <https://debuginfod.archlinux.org>
Enable debuginfod for this session? (y or [n]) 
Debuginfod has been disabled.
To make this setting permanent, add 'set debuginfod enabled off' to .gdbinit.
(No debugging symbols found in ./l-vs-g)

(gdb) b main
Breakpoint 1 at 0x113d

(gdb) r
Starting program: /home/sergey/l-vs-g 
[Thread debugging using libthread_db enabled]
Using host libthread_db library "/usr/lib/libthread_db.so.1".

Breakpoint 1, 0x000055555555513d in main ()

(gdb) disas main
Dump of assembler code for function main:
   0x0000555555555139 <+0>:	push   %rbp
   0x000055555555513a <+1>:	mov    %rsp,%rbp
=> 0x000055555555513d <+4>:	sub    $0x10,%rsp
   0x0000555555555141 <+8>:	movl   $0x64,-0x4(%rbp)                              // local X = 100
   0x0000555555555148 <+15>:	mov    0x2ece(%rip),%edx       # 0x55555555801c <y>  // global Y
   0x000055555555514e <+21>:	mov    -0x4(%rbp),%eax
   0x0000555555555151 <+24>:	lea    0xeac(%rip),%rcx        # 0x555555556004      // global format string
   0x0000555555555158 <+31>:	mov    %eax,%esi
   0x000055555555515a <+33>:	mov    %rcx,%rdi
   0x000055555555515d <+36>:	mov    $0x0,%eax
   0x0000555555555162 <+41>:	call   0x555555555030 <printf@plt>
   0x0000555555555167 <+46>:	call   0x555555555173 <g>
   0x000055555555516c <+51>:	mov    $0x0,%eax
   0x0000555555555171 <+56>:	leave
   0x0000555555555172 <+57>:	ret
End of assembler dump.

(gdb) disas g
Dump of assembler code for function g:
   0x0000555555555173 <+0>:	push   %rbp
   0x0000555555555174 <+1>:	mov    %rsp,%rbp
   0x0000555555555177 <+4>:	mov    0x2e9f(%rip),%edx        # 0x55555555801c <y>   // global 
   0x000055555555517d <+10>:	mov    0x2e95(%rip),%eax        # 0x555555558018 <x>   // global
   0x0000555555555183 <+16>:	lea    0xe88(%rip),%rcx         # 0x555555556012       // format string
   0x000055555555518a <+23>:	mov    %eax,%esi
   0x000055555555518c <+25>:	mov    %rcx,%rdi
   0x000055555555518f <+28>:	mov    $0x0,%eax           // reminder: this is a printf() special
   0x0000555555555194 <+33>:	call   0x555555555030 <printf@plt>
   0x0000555555555199 <+38>:	lea    0x2e7c(%rip),%rdx        # 0x55555555801c <y>   // LEA gets the address where MOV gets the value of the memory cell 
   0x00005555555551a0 <+45>:	lea    0x2e71(%rip),%rcx        # 0x555555558018 <x>
   0x00005555555551a7 <+52>:	lea    0xe72(%rip),%rax         # 0x555555556020
   0x00005555555551ae <+59>:	mov    %rcx,%rsi
   0x00005555555551b1 <+62>:	mov    %rax,%rdi
   0x00005555555551b4 <+65>:	mov    $0x0,%eax
   0x00005555555551b9 <+70>:	call   0x555555555030 <printf@plt>
   0x00005555555551be <+75>:	nop
   0x00005555555551bf <+76>:	pop    %rbp
   0x00005555555551c0 <+77>:	ret
End of assembler dump.

// let's check the content of absolute addresses:

(gdb) x/s 0x555555556004
0x555555556004:	"f: x=%d y=%d\n"

(gdb) x/1xw 0x55555555801c
0x55555555801c <y>:	0x000000c8   // viewed as hex

(gdb) x/1dw 0x55555555801c
0x55555555801c <y>:	200          // viewed as decimal

(gdb) disas g
Dump of assembler code for function g:
   0x0000555555555173 <+0>:	push   %rbp
   0x0000555555555174 <+1>:	mov    %rsp,%rbp
   0x0000555555555177 <+4>:	mov    0x2e9f(%rip),%edx        # 0x55555555801c <y>  
   0x000055555555517d <+10>:	mov    0x2e95(%rip),%eax        # 0x555555558018 <x>
   0x0000555555555183 <+16>:	lea    0xe88(%rip),%rcx        # 0x555555556012
   0x000055555555518a <+23>:	mov    %eax,%esi
   0x000055555555518c <+25>:	mov    %rcx,%rdi
   0x000055555555518f <+28>:	mov    $0x0,%eax
   0x0000555555555194 <+33>:	call   0x555555555030 <printf@plt>
   0x0000555555555199 <+38>:	lea    0x2e7c(%rip),%rdx        # 0x55555555801c <y>

// Note the shift in offsets. Since these global addresses are addressed as offsets
// of the current instruction, the offsets to the same global address change with every instruction

   0x00005555555551a0 <+45>:	lea    0x2e71(%rip),%rcx        # 0x555555558018 <x>  // same here
   0x00005555555551a7 <+52>:	lea    0xe72(%rip),%rax        # 0x555555556020       // same here
   0x00005555555551ae <+59>:	mov    %rcx,%rsi
   0x00005555555551b1 <+62>:	mov    %rax,%rdi
   0x00005555555551b4 <+65>:	mov    $0x0,%eax
   0x00005555555551b9 <+70>:	call   0x555555555030 <printf@plt>
   0x00005555555551be <+75>:	nop
   0x00005555555551bf <+76>:	pop    %rbp
   0x00005555555551c0 <+77>:	ret
End of assembler dump.

(gdb) x/s 0x555555556012
0x555555556012:	"g: x=%d y=%d\n"

(gdb) x/1dw 0x55555555801c
0x55555555801c <y>:	200        // global value

(gdb) x/1dw 0x555555558018
0x555555558018 <x>:	1          // local value

(gdb) x/s 0x555555556020
0x555555556020:	"&x=%p &y=%p\n"

// Let's go back to the factorial example and see what happens if we change
//   unsigned int (4 byte integer) into long long (8 byte integer):

[sergey@thepond ~]$ cat factq.c
#include <stdio.h>

/* a very naive recursive factorial */
long long fact(long long  n)
{
     printf("%p %d\n", &n, n);  // print addresses of "n" in each frame
     if( n == 0 )
          return 1;
     return n * fact(n-1);
}

int main()
{
     printf("%d\n", fact(7));
     return 0;
}

[sergey@thepond ~]$ gcc -o factq factq.c

[sergey@thepond ~]$ gdb ./factq
GNU gdb (GDB) 16.3
Copyright (C) 2024 Free Software Foundation, Inc.
License GPLv3+: GNU GPL version 3 or later <http://gnu.org/licenses/gpl.html>
// ... skipped ...
(No debugging symbols found in ./factq)

(gdb) b fact
Breakpoint 1 at 0x113d

(gdb) ignore 1 6
Will ignore next 6 crossings of breakpoint 1.

(gdb) r
Starting program: /home/sergey/factq 
[Thread debugging using libthread_db enabled]
Using host libthread_db library "/usr/lib/libthread_db.so.1".
0x7fffffffeaa8 7       // <--- we see the addresses of "n" in each frame
0x7fffffffea88 6
0x7fffffffea68 5
0x7fffffffea48 4
0x7fffffffea28 3
0x7fffffffea08 2

Breakpoint 1, 0x000055555555513d in fact ()

(gdb) i r rdi          // the argument is 1, this is the call to fact(1)  
rdi            0x1                 1

// Let's see the stack: 

(gdb) x/28xg $rsp
0x7fffffffe9f0:	0x00007fffffffea10	0x0000555555555184  // return address in fact()
0x7fffffffea00:	0x00007ffff7e09680	0x0000000000000002  // <-- n=2, 8-byte int
0x7fffffffea10:	0x00007fffffffea30	0x0000555555555184
0x7fffffffea20:	0x0000000000000000	0x0000000000000003  // <-- n=3 
0x7fffffffea30:	0x00007fffffffea50	0x0000555555555184
0x7fffffffea40:	0xffffffffffffffff	0x0000000000000004  // <-- n=4 
0x7fffffffea50:	0x00007fffffffea70	0x0000555555555184
0x7fffffffea60:	0x0000000000940000	0x0000000000000005
0x7fffffffea70:	0x00007fffffffea90	0x0000555555555184
0x7fffffffea80:	0x0000000000000000	0x0000000000000006
0x7fffffffea90:	0x00007fffffffeab0	0x0000555555555184
0x7fffffffeaa0:	0x0000000000000000	0x0000000000000007
0x7fffffffeab0:	0x00007fffffffeac0	0x000055555555519c  // return address in main() 
0x7fffffffeac0:	0x00007fffffffeb60	0x00007ffff7c27675

(gdb) disas 
Dump of assembler code for function fact:
   0x0000555555555139 <+0>:	push   %rbp
   0x000055555555513a <+1>:	mov    %rsp,%rbp
=> 0x000055555555513d <+4>:	sub    $0x10,%rsp
   0x0000555555555141 <+8>:	mov    %rdi,-0x8(%rbp)   // "n" is now 8 bytes, compared to 4 previously
   0x0000555555555145 <+12>:	mov    -0x8(%rbp),%rdx   
   0x0000555555555149 <+16>:	lea    -0x8(%rbp),%rax
   0x000055555555514d <+20>:	lea    0xeb0(%rip),%rcx        # 0x555555556004
   0x0000555555555154 <+27>:	mov    %rax,%rsi
   0x0000555555555157 <+30>:	mov    %rcx,%rdi
   0x000055555555515a <+33>:	mov    $0x0,%eax
   0x000055555555515f <+38>:	call   0x555555555030 <printf@plt>
   0x0000555555555164 <+43>:	mov    -0x8(%rbp),%rax
   0x0000555555555168 <+47>:	test   %rax,%rax
   0x000055555555516b <+50>:	jne    0x555555555174 <fact+59>
   0x000055555555516d <+52>:	mov    $0x1,%eax
   0x0000555555555172 <+57>:	jmp    0x55555555518c <fact+83>
   0x0000555555555174 <+59>:	mov    -0x8(%rbp),%rax
   0x0000555555555178 <+63>:	sub    $0x1,%rax
   0x000055555555517c <+67>:	mov    %rax,%rdi
   0x000055555555517f <+70>:	call   0x555555555139 <fact>  // call to self
   0x0000555555555184 <+75>:	mov    -0x8(%rbp),%rdx        // return here after call to self
   0x0000555555555188 <+79>:	imul   %rdx,%rax
   0x000055555555518c <+83>:	leave
   0x000055555555518d <+84>:	ret
End of assembler dump.
(gdb) 

// Let's see the stack being unwound. At each point right after fact()'s call to self,
//   let's print the value returned in RAX (and continue automatically, to save some keypresses):

(gdb) b *0x0000555555555184
Breakpoint 2 at 0x555555555184

(gdb) commands 2
Type commands for breakpoint(s) 2, one per line.
End with a line saying just "end".
>printf "$rax = 0x%lx\n", $rax
>continue
>end

(gdb) c
Continuing.
0x7fffffffe9e8 1

Breakpoint 1, 0x000055555555513d in fact ()     // <<-- Oops, I hit a breakpoint on one last entry
                                                //       to fact(). Let's just delete it. 
(gdb) del 1

(gdb) c
Continuing.
0x7fffffffe9c8 0

Breakpoint 2, 0x0000555555555184 in fact ()
$rax = 0x1                                    // returning from fact(0)

Breakpoint 2, 0x0000555555555184 in fact ()   // returning from fact(1)
$rax = 0x1

Breakpoint 2, 0x0000555555555184 in fact ()   // returning from fact(2)
$rax = 0x2

Breakpoint 2, 0x0000555555555184 in fact ()   // returning from fact(3)
$rax = 0x6

Breakpoint 2, 0x0000555555555184 in fact ()   // returning from fact(4), that's decimal 24  
$rax = 0x18

Breakpoint 2, 0x0000555555555184 in fact ()   // returning from fact(5), decimal 120 
$rax = 0x78

Breakpoint 2, 0x0000555555555184 in fact ()   // returning from fact(6), decimal 720
$rax = 0x2d0

5040
[Inferior 1 (process 479660) exited normally]