写点关于递归的话题（一）

刚写了2颗树，里面用到了递归，顺着这个就随便写点关于递归的问题。这些问题都比较初级，也正应了这个blog的名字，当作一个学习和复习问题的笔记罢了。

记得我上学那会，C语言老师讲melloc内存那会就不理解为什么不直接用数组，因为当时不懂的东西太多，也不差这一个，所以也没放在心上。

后来就知道了数组是直接在线程栈上面开辟空间，而melloc则是使用系统堆来分配空间。（当然，这只是一个浅显的理解，操作系统后台的内存分配比这要复杂的多得多，比如windows下面有保留内存、堆和文件映射内存等多种内存分配方式来适应各种大小、类别内存分配的需求，melloc的实现还没有仔细研究过）

而线程栈的大小是有限制的，对于我自己使用的x86_64 linux系统，默认是8M（使用ulimit -s来查看），一旦超过了这个大小，程序就直接崩溃了。(这个问题涉及到x86分段机制，比刚才那个问题更加底层)。

因此，对于栈空间的使用一定要非常谨慎。每次递归都会在栈中消耗空间，因此递归的空间复杂度决定了这个递归是不是安全的。

首先，来看看究竟这究竟是怎么一个过程。

先用我微不足道的c语言知识写一个简单的求和的递归程序

int sum(int n)
{
if(n==1)
return 1;
else
return n+sum(n-1);
}
int main()
{
int n=5;
int s;
s=sum(n);
}

编译并连接，使用objdump -D 来进行反汇编，得到如下结果

rec：
文件格式 elf64-x86-64
Disassembly of section .interp:
0000000000400238 <.interp>:
400238:
2f
(bad)
400239:
6c
insb
(%dx),%es:(%rdi)
40023a:
69 62 36 34 2f 6c 64
imul
$0x646c2f34,0x36(%rdx),%esp
400241:
2d 6c 69 6e 75
sub
$0x756e696c,%eax
400246:
78 2d
js
400275 <_init-0x133>
400248:
78 38
js
400282 <_init-0x126>
40024a:
36
ss
40024b:
2d 36 34 2e 73
sub
$0x732e3436,%eax
400250:
6f
outsl
%ds:(%rsi),(%dx)
400251:
2e 32 00
xor
%cs:(%rax),%al
Disassembly of section .note.ABI-tag:
0000000000400254 <.note.ABI-tag>:
400254:
04 00
add
$0x0,%al
400256:
00 00
add
%al,(%rax)
400258:
10 00
adc
%al,(%rax)
40025a:
00 00
add
%al,(%rax)
40025c:
01 00
add
%eax,(%rax)
40025e:
00 00
add
%al,(%rax)
400260:
47
rex.RXB
400261:
4e 55
rex.WRX push %rbp
400263:
00 00
add
%al,(%rax)
400265:
00 00
add
%al,(%rax)
400267:
00 02
add
%al,(%rdx)
400269:
00 00
add
%al,(%rax)
40026b:
00 06
add
%al,(%rsi)
40026d:
00 00
add
%al,(%rax)
40026f:
00 18
add
%bl,(%rax)
400271:
00 00
add
%al,(%rax)
...
Disassembly of section .note.gnu.build-id:
0000000000400274 <.note.gnu.build-id>:
400274:
04 00
add
$0x0,%al
400276:
00 00
add
%al,(%rax)
400278:
14 00
adc
$0x0,%al
40027a:
00 00
add
%al,(%rax)
40027c:
03 00
add
(%rax),%eax
40027e:
00 00
add
%al,(%rax)
400280:
47
rex.RXB
400281:
4e 55
rex.WRX push %rbp
400283:
00 78 c1
add
%bh,-0x3f(%rax)
400286:
f9
stc
400287:
a6
cmpsb
%es:(%rdi),%ds:(%rsi)
400288:
6f
outsl
%ds:(%rsi),(%dx)
400289:
fd
std
40028a:
a7
cmpsl
%es:(%rdi),%ds:(%rsi)
40028b:
9f
lahf
40028c:
dc 12
fcoml
(%rdx)
40028e:
a7
cmpsl
%es:(%rdi),%ds:(%rsi)
40028f:
b1 d1
mov
$0xd1,%cl
400291:
d9 cc
fxch
%st(4)
400293:
9f
lahf
400294:
dc 2f
fsubrl (%rdi)
400296:
d1 13
rcll
(%rbx)
Disassembly of section .gnu.hash:
0000000000400298 <.gnu.hash>:
400298:
01 00
add
%eax,(%rax)
40029a:
00 00
add
%al,(%rax)
40029c:
01 00
add
%eax,(%rax)
40029e:
00 00
add
%al,(%rax)
4002a0:
01 00
add
%eax,(%rax)
...
Disassembly of section .dynsym:
00000000004002b8 <.dynsym>:
...
4002d0:
0b 00
or
(%rax),%eax
4002d2:
00 00
add
%al,(%rax)
4002d4:
12 00
adc
(%rax),%al
...
4002e6:
00 00
add
%al,(%rax)
4002e8:
1d 00 00 00 20
sbb
$0x20000000,%eax
...
Disassembly of section .dynstr:
0000000000400300 <.dynstr>:
400300:
00 6c 69 62
add
%ch,0x62(%rcx,%rbp,2)
400304:
63 2e
movslq (%rsi),%ebp
400306:
73 6f
jae
400377 <_init-0x31>
400308:
2e 36 00 5f 5f
cs add %bl,%cs:%ss:0x5f(%rdi)
40030d:
6c
insb
(%dx),%es:(%rdi)
40030e:
69 62 63 5f 73 74 61
imul
$0x6174735f,0x63(%rdx),%esp
400315:
72 74
jb
40038b <_init-0x1d>
400317:
5f
pop
%rdi
400318:
6d
insl
(%dx),%es:(%rdi)
400319:
61
(bad)
40031a:
69 6e 00 5f 5f 67 6d
imul
$0x6d675f5f,0x0(%rsi),%ebp
400321:
6f
outsl
%ds:(%rsi),(%dx)
400322:
6e
outsb
%ds:(%rsi),(%dx)
400323:
5f
pop
%rdi
400324:
73 74
jae
40039a <_init-0xe>
400326:
61
(bad)
400327:
72 74
jb
40039d <_init-0xb>
400329:
5f
pop
%rdi
40032a:
5f
pop
%rdi
40032b:
00 47 4c
add
%al,0x4c(%rdi)
40032e:
49
rex.WB
40032f:
42
rex.X
400330:
43 5f
rex.XB pop %r15
400332:
32 2e
xor
(%rsi),%ch
400334:
32 2e
xor
(%rsi),%ch
400336:
35
.byte 0x35
...
Disassembly of section .gnu.version:
0000000000400338 <.gnu.version>:
400338:
00 00
add
%al,(%rax)
40033a:
02 00
add
(%rax),%al
...
Disassembly of section .gnu.version_r:
0000000000400340 <.gnu.version_r>:
400340:
01 00
add
%eax,(%rax)
400342:
01 00
add
%eax,(%rax)
400344:
01 00
add
%eax,(%rax)
400346:
00 00
add
%al,(%rax)
400348:
10 00
adc
%al,(%rax)
40034a:
00 00
add
%al,(%rax)
40034c:
00 00
add
%al,(%rax)
40034e:
00 00
add
%al,(%rax)
400350:
75 1a
jne
40036c <_init-0x3c>
400352:
69 09 00 00 02 00
imul
$0x20000,(%rcx),%ecx
400358:
2c 00
sub
$0x0,%al
40035a:
00 00
add
%al,(%rax)
40035c:
00 00
add
%al,(%rax)
...
Disassembly of section .rela.dyn:
0000000000400360 <.rela.dyn>:
400360:
f8
clc
400361:
0f 60 00
punpcklbw (%rax),%mm0
400364:
00 00
add
%al,(%rax)
400366:
00 00
add
%al,(%rax)
400368:
06
(bad)
400369:
00 00
add
%al,(%rax)
40036b:
00 02
add
%al,(%rdx)
...
Disassembly of section .rela.plt:
0000000000400378 <.rela.plt>:
400378:
18 10
sbb
%dl,(%rax)
40037a:
60
(bad)
40037b:
00 00
add
%al,(%rax)
40037d:
00 00
add
%al,(%rax)
40037f:
00 07
add
%al,(%rdi)
400381:
00 00
add
%al,(%rax)
400383:
00 01
add
%al,(%rcx)
...
40038d:
00 00
add
%al,(%rax)
40038f:
00 20
add
%ah,(%rax)
400391:
10 60 00
adc
%ah,0x0(%rax)
400394:
00 00
add
%al,(%rax)
400396:
00 00
add
%al,(%rax)
400398:
07
(bad)
400399:
00 00
add
%al,(%rax)
40039b:
00 02
add
%al,(%rdx)
...
Disassembly of section .init:
00000000004003a8 <_init>:
4003a8:
48 83 ec 08
sub
$0x8,%rsp
4003ac:
48 8b 05 45 0c 20 00
mov
0x200c45(%rip),%rax
# 600ff8 <_DYNAMIC+0x1d0>
4003b3:
48 85 c0
test
%rax,%rax
4003b6:
74 05
je
4003bd <_init+0x15>
4003b8:
e8 33 00 00 00
callq
4003f0 <__gmon_start__@plt>
4003bd:
48 83 c4 08
add
$0x8,%rsp
4003c1:
c3
retq
Disassembly of section .plt:
00000000004003d0 <__libc_start_main@plt-0x10>:
4003d0:
ff 35 32 0c 20 00
pushq
0x200c32(%rip)
# 601008 <_GLOBAL_OFFSET_TABLE_+0x8>
4003d6:
ff 25 34 0c 20 00
jmpq
*0x200c34(%rip)
# 601010 <_GLOBAL_OFFSET_TABLE_+0x10>
4003dc:
0f 1f 40 00
nopl
0x0(%rax)
00000000004003e0 <__libc_start_main@plt>:
4003e0:
ff 25 32 0c 20 00
jmpq
*0x200c32(%rip)
# 601018 <_GLOBAL_OFFSET_TABLE_+0x18>
4003e6:
68 00 00 00 00
pushq
$0x0
4003eb:
e9 e0 ff ff ff
jmpq
4003d0 <_init+0x28>
00000000004003f0 <__gmon_start__@plt>:
4003f0:
ff 25 2a 0c 20 00
jmpq
*0x200c2a(%rip)
# 601020 <_GLOBAL_OFFSET_TABLE_+0x20>
4003f6:
68 01 00 00 00
pushq
$0x1
4003fb:
e9 d0 ff ff ff
jmpq
4003d0 <_init+0x28>
Disassembly of section .text:
0000000000400400 <_start>:
400400:
31 ed
xor
%ebp,%ebp
400402:
49 89 d1
mov
%rdx,%r9
400405:
5e
pop
%rsi
400406:
48 89 e2
mov
%rsp,%rdx
400409:
48 83 e4 f0
and
$0xfffffffffffffff0,%rsp
40040d:
50
push
%rax
40040e:
54
push
%rsp
40040f:
49 c7 c0 d0 05 40 00
mov
$0x4005d0,%r8
400416:
48 c7 c1 40 05 40 00
mov
$0x400540,%rcx
40041d:
48 c7 c7 18 05 40 00
mov
$0x400518,%rdi
400424:
e8 b7 ff ff ff
callq
4003e0 <__libc_start_main@plt>
400429:
f4
hlt
40042a:
66 90
xchg
%ax,%ax
40042c:
0f 1f 40 00
nopl
0x0(%rax)
0000000000400430 <deregister_tm_clones>:
400430:
b8 3f 10 60 00
mov
$0x60103f,%eax
400435:
55
push
%rbp
400436:
48 2d 38 10 60 00
sub
$0x601038,%rax
40043c:
48 83 f8 0e
cmp
$0xe,%rax
400440:
48 89 e5
mov
%rsp,%rbp
400443:
77 02
ja
400447 <deregister_tm_clones+0x17>
400445:
5d
pop
%rbp
400446:
c3
retq
400447:
b8 00 00 00 00
mov
$0x0,%eax
40044c:
48 85 c0
test
%rax,%rax
40044f:
74 f4
je
400445 <deregister_tm_clones+0x15>
400451:
5d
pop
%rbp
400452:
bf 38 10 60 00
mov
$0x601038,%edi
400457:
ff e0
jmpq
*%rax
400459:
0f 1f 80 00 00 00 00
nopl
0x0(%rax)
0000000000400460 <register_tm_clones>:
400460:
b8 38 10 60 00
mov
$0x601038,%eax
400465:
55
push
%rbp
400466:
48 2d 38 10 60 00
sub
$0x601038,%rax
40046c:
48 c1 f8 03
sar
$0x3,%rax
400470:
48 89 e5
mov
%rsp,%rbp
400473:
48 89 c2
mov
%rax,%rdx
400476:
48 c1 ea 3f
shr
$0x3f,%rdx
40047a:
48 01 d0
add
%rdx,%rax
40047d:
48 89 c6
mov
%rax,%rsi
400480:
48 d1 fe
sar
%rsi
400483:
75 02
jne
400487 <register_tm_clones+0x27>
400485:
5d
pop
%rbp
400486:
c3
retq
400487:
ba 00 00 00 00
mov
$0x0,%edx
40048c:
48 85 d2
test
%rdx,%rdx
40048f:
74 f4
je
400485 <register_tm_clones+0x25>
400491:
5d
pop
%rbp
400492:
bf 38 10 60 00
mov
$0x601038,%edi
400497:
ff e2
jmpq
*%rdx
400499:
0f 1f 80 00 00 00 00
nopl
0x0(%rax)
00000000004004a0 <__do_global_dtors_aux>:
4004a0:
80 3d 91 0b 20 00 00
cmpb
$0x0,0x200b91(%rip)
# 601038 <__TMC_END__>
4004a7:
75 11
jne
4004ba <__do_global_dtors_aux+0x1a>
4004a9:
55
push
%rbp
4004aa:
48 89 e5
mov
%rsp,%rbp
4004ad:
e8 7e ff ff ff
callq
400430 <deregister_tm_clones>
4004b2:
5d
pop
%rbp
4004b3:
c6 05 7e 0b 20 00 01
movb
$0x1,0x200b7e(%rip)
# 601038 <__TMC_END__>
4004ba:
f3 c3
repz retq
4004bc:
0f 1f 40 00
nopl
0x0(%rax)
00000000004004c0 <frame_dummy>:
4004c0:
48 83 3d 58 09 20 00
cmpq
$0x0,0x200958(%rip)
# 600e20 <__JCR_END__>
4004c7:
00
4004c8:
74 1b
je
4004e5 <frame_dummy+0x25>
4004ca:
b8 00 00 00 00
mov
$0x0,%eax
4004cf:
48 85 c0
test
%rax,%rax
4004d2:
74 11
je
4004e5 <frame_dummy+0x25>
4004d4:
55
push
%rbp
4004d5:
bf 20 0e 60 00
mov
$0x600e20,%edi
4004da:
48 89 e5
mov
%rsp,%rbp
4004dd:
ff d0
callq
*%rax
4004df:
5d
pop
%rbp
4004e0:
e9 7b ff ff ff
jmpq
400460 <register_tm_clones>
4004e5:
e9 76 ff ff ff
jmpq
400460 <register_tm_clones>
4004ea:
66 90
xchg
%ax,%ax
00000000004004ec <sum>:
4004ec:
55
push
%rbp
4004ed:
48 89 e5
mov
%rsp,%rbp
4004f0:
48 83 ec 10
sub
$0x10,%rsp
4004f4:
89 7d fc
mov
%edi,-0x4(%rbp)
4004f7:
83 7d fc 01
cmpl
$0x1,-0x4(%rbp)
4004fb:
75 07
jne
400504 <sum+0x18>
4004fd:
b8 01 00 00 00
mov
$0x1,%eax
400502:
eb 12
jmp
400516 <sum+0x2a>
400504:
8b 45 fc
mov
-0x4(%rbp),%eax
400507:
83 e8 01
sub
$0x1,%eax
40050a:
89 c7
mov
%eax,%edi
40050c:
e8 db ff ff ff
callq
4004ec <sum>
400511:
8b 55 fc
mov
-0x4(%rbp),%edx
400514:
01 d0
add
%edx,%eax
400516:
c9
leaveq
400517:
c3
retq
0000000000400518 <main>:
400518:
55
push
%rbp
400519:
48 89 e5
mov
%rsp,%rbp
40051c:
48 83 ec 10
sub
$0x10,%rsp
400520:
c7 45 f8 05 00 00 00
movl
$0x5,-0x8(%rbp)
400527:
8b 45 f8
mov
-0x8(%rbp),%eax
40052a:
89 c7
mov
%eax,%edi
40052c:
e8 bb ff ff ff
callq
4004ec <sum>
400531:
89 45 fc
mov
%eax,-0x4(%rbp)
400534:
c9
leaveq
400535:
c3
retq
400536:
66 2e 0f 1f 84 00 00
nopw
%cs:0x0(%rax,%rax,1)
40053d:
00 00 00
0000000000400540 <__libc_csu_init>:
400540:
48 89 6c 24 d8
mov
%rbp,-0x28(%rsp)
400545:
4c 89 64 24 e0
mov
%r12,-0x20(%rsp)
40054a:
48 8d 2d c7 08 20 00
lea
0x2008c7(%rip),%rbp
# 600e18 <__init_array_end>
400551:
4c 8d 25 b8 08 20 00
lea
0x2008b8(%rip),%r12
# 600e10 <__frame_dummy_init_array_entry>
400558:
48 89 5c 24 d0
mov
%rbx,-0x30(%rsp)
40055d:
4c 89 6c 24 e8
mov
%r13,-0x18(%rsp)
400562:
4c 89 74 24 f0
mov
%r14,-0x10(%rsp)
400567:
4c 89 7c 24 f8
mov
%r15,-0x8(%rsp)
40056c:
48 83 ec 38
sub
$0x38,%rsp
400570:
4c 29 e5
sub
%r12,%rbp
400573:
41 89 ff
mov
%edi,%r15d
400576:
49 89 f6
mov
%rsi,%r14
400579:
48 c1 fd 03
sar
$0x3,%rbp
40057d:
49 89 d5
mov
%rdx,%r13
400580:
31 db
xor
%ebx,%ebx
400582:
e8 21 fe ff ff
callq
4003a8 <_init>
400587:
48 85 ed
test
%rbp,%rbp
40058a:
74 1a
je
4005a6 <__libc_csu_init+0x66>
40058c:
0f 1f 40 00
nopl
0x0(%rax)
400590:
4c 89 ea
mov
%r13,%rdx
400593:
4c 89 f6
mov
%r14,%rsi
400596:
44 89 ff
mov
%r15d,%edi
400599:
41 ff 14 dc
callq
*(%r12,%rbx,8)
40059d:
48 83 c3 01
add
$0x1,%rbx
4005a1:
48 39 eb
cmp
%rbp,%rbx
4005a4:
75 ea
jne
400590 <__libc_csu_init+0x50>
4005a6:
48 8b 5c 24 08
mov
0x8(%rsp),%rbx
4005ab:
48 8b 6c 24 10
mov
0x10(%rsp),%rbp
4005b0:
4c 8b 64 24 18
mov
0x18(%rsp),%r12
4005b5:
4c 8b 6c 24 20
mov
0x20(%rsp),%r13
4005ba:
4c 8b 74 24 28
mov
0x28(%rsp),%r14
4005bf:
4c 8b 7c 24 30
mov
0x30(%rsp),%r15
4005c4:
48 83 c4 38
add
$0x38,%rsp
4005c8:
c3
retq
4005c9:
0f 1f 80 00 00 00 00
nopl
0x0(%rax)
00000000004005d0 <__libc_csu_fini>:
4005d0:
f3 c3
repz retq
4005d2:
66 90
xchg
%ax,%ax
Disassembly of section .fini:
00000000004005d4 <_fini>:
4005d4:
48 83 ec 08
sub
$0x8,%rsp
4005d8:
48 83 c4 08
add
$0x8,%rsp
4005dc:
c3
retq
Disassembly of section .rodata:
00000000004005e0 <_IO_stdin_used>:
4005e0:
01 00
add
%eax,(%rax)
4005e2:
02 00
add
(%rax),%al
Disassembly of section .eh_frame_hdr:
00000000004005e4 <.eh_frame_hdr>:
4005e4:
01 1b
add
%ebx,(%rbx)
4005e6:
03 3b
add
(%rbx),%edi
4005e8:
38 00
cmp
%al,(%rax)
4005ea:
00 00
add
%al,(%rax)
4005ec:
06
(bad)
4005ed:
00 00
add
%al,(%rax)
4005ef:
00 ec
add
%ch,%ah
4005f1:
fd
std
4005f2:
ff
(bad)
4005f3:
ff 84 00 00 00 1c fe
incl
-0x1e40000(%rax,%rax,1)
4005fa:
ff
(bad)
4005fb:
ff 54 00 00
callq
*0x0(%rax,%rax,1)
4005ff:
00 08
add
%cl,(%rax)
400601:
ff
(bad)
400602:
ff
(bad)
400603:
ff ac 00 00 00 34 ff
ljmpq
*-0xcc0000(%rax,%rax,1)
40060a:
ff
(bad)
40060b:
ff cc
dec
%esp
40060d:
00 00
add
%al,(%rax)
40060f:
00 5c ff ff
add
%bl,-0x1(%rdi,%rdi,8)
400613:
ff ec
ljmpq
*<反汇编器内部错误>
400615:
00 00
add
%al,(%rax)
400617:
00 ec
add
%ch,%ah
400619:
ff
(bad)
40061a:
ff
(bad)
40061b:
ff 14 01
callq
*(%rcx,%rax,1)
...
Disassembly of section .eh_frame:
0000000000400620 <__FRAME_END__-0xf0>:
400620:
14 00
adc
$0x0,%al
400622:
00 00
add
%al,(%rax)
400624:
00 00
add
%al,(%rax)
400626:
00 00
add
%al,(%rax)
400628:
01 7a 52
add
%edi,0x52(%rdx)
40062b:
00 01
add
%al,(%rcx)
40062d:
78 10
js
40063f <_IO_stdin_used+0x5f>
40062f:
01 1b
add
%ebx,(%rbx)
400631:
0c 07
or
$0x7,%al
400633:
08 90 01 07 10 14
or
%dl,0x14100701(%rax)
400639:
00 00
add
%al,(%rax)
40063b:
00 1c 00
add
%bl,(%rax,%rax,1)
40063e:
00 00
add
%al,(%rax)
400640:
c0 fd ff
sar
$0xff,%ch
400643:
ff 2a
ljmpq
*(%rdx)
...
40064d:
00 00
add
%al,(%rax)
40064f:
00 14 00
add
%dl,(%rax,%rax,1)
400652:
00 00
add
%al,(%rax)
400654:
00 00
add
%al,(%rax)
400656:
00 00
add
%al,(%rax)
400658:
01 7a 52
add
%edi,0x52(%rdx)
40065b:
00 01
add
%al,(%rcx)
40065d:
78 10
js
40066f <_IO_stdin_used+0x8f>
40065f:
01 1b
add
%ebx,(%rbx)
400661:
0c 07
or
$0x7,%al
400663:
08 90 01 00 00 24
or
%dl,0x24000001(%rax)
400669:
00 00
add
%al,(%rax)
40066b:
00 1c 00
add
%bl,(%rax,%rax,1)
40066e:
00 00
add
%al,(%rax)
400670:
60
(bad)
400671:
fd
std
400672:
ff
(bad)
400673:
ff 30
pushq
(%rax)
400675:
00 00
add
%al,(%rax)
400677:
00 00
add
%al,(%rax)
400679:
0e
(bad)
40067a:
10 46 0e
adc
%al,0xe(%rsi)
40067d:
18 4a 0f
sbb
%cl,0xf(%rdx)
400680:
0b 77 08
or
0x8(%rdi),%esi
400683:
80 00 3f
addb
$0x3f,(%rax)
400686:
1a 3b
sbb
(%rbx),%bh
400688:
2a 33
sub
(%rbx),%dh
40068a:
24 22
and
$0x22,%al
40068c:
00 00
add
%al,(%rax)
40068e:
00 00
add
%al,(%rax)
400690:
1c 00
sbb
$0x0,%al
400692:
00 00
add
%al,(%rax)
400694:
44 00 00
add
%r8b,(%rax)
400697:
00 54 fe ff
add
%dl,-0x1(%rsi,%rdi,8)
40069b:
ff 2c 00
ljmpq
*(%rax,%rax,1)
40069e:
00 00
add
%al,(%rax)
4006a0:
00 41 0e
add
%al,0xe(%rcx)
4006a3:
10 86 02 43 0d 06
adc
%al,0x60d4302(%rsi)
4006a9:
67 0c 07
addr32 or $0x7,%al
4006ac:
08 00
or
%al,(%rax)
4006ae:
00 00
add
%al,(%rax)
4006b0:
1c 00
sbb
$0x0,%al
4006b2:
00 00
add
%al,(%rax)
4006b4:
64 00 00
add
%al,%fs:(%rax)
4006b7:
00 60 fe
add
%ah,-0x2(%rax)
4006ba:
ff
(bad)
4006bb:
ff 1e
lcallq *(%rsi)
4006bd:
00 00
add
%al,(%rax)
4006bf:
00 00
add
%al,(%rax)
4006c1:
41 0e
rex.B (bad)
4006c3:
10 86 02 43 0d 06
adc
%al,0x60d4302(%rsi)
4006c9:
59
pop
%rcx
4006ca:
0c 07
or
$0x7,%al
4006cc:
08 00
or
%al,(%rax)
4006ce:
00 00
add
%al,(%rax)
4006d0:
24 00
and
$0x0,%al
4006d2:
00 00
add
%al,(%rax)
4006d4:
84 00
test
%al,(%rax)
4006d6:
00 00
add
%al,(%rax)
4006d8:
68 fe ff ff 89
pushq
$0xffffffff89fffffe
4006dd:
00 00
add
%al,(%rax)
4006df:
00 00
add
%al,(%rax)
4006e1:
4a 86 06
rex.WX xchg %al,(%rsi)
4006e4:
8c 05 66 0e 40 83
mov
%es,-0x7cbff19a(%rip)
# ffffffff83801550 <_end+0xffffffff83200510>
4006ea:
07
(bad)
4006eb:
8d 04 8e
lea
(%rsi,%rcx,4),%eax
4006ee:
03 8f 02 02 58 0e
add
0xe580202(%rdi),%ecx
4006f4:
08 00
or
%al,(%rax)
4006f6:
00 00
add
%al,(%rax)
4006f8:
14 00
adc
$0x0,%al
4006fa:
00 00
add
%al,(%rax)
4006fc:
ac
lods
%ds:(%rsi),%al
4006fd:
00 00
add
%al,(%rax)
4006ff:
00 d0
add
%dl,%al
400701:
fe
(bad)
400702:
ff
(bad)
400703:
ff 02
incl
(%rdx)
...
0000000000400710 <__FRAME_END__>:
400710:
00 00
add
%al,(%rax)
...
Disassembly of section .init_array:
0000000000600e10 <__frame_dummy_init_array_entry>:
600e10:
c0 04 40 00
rolb
$0x0,(%rax,%rax,2)
600e14:
00 00
add
%al,(%rax)
...
Disassembly of section .fini_array:
0000000000600e18 <__do_global_dtors_aux_fini_array_entry>:
600e18:
a0
.byte 0xa0
600e19:
04 40
add
$0x40,%al
600e1b:
00 00
add
%al,(%rax)
600e1d:
00 00
add
%al,(%rax)
...
Disassembly of section .jcr:
0000000000600e20 <__JCR_END__>:
...
Disassembly of section .dynamic:
0000000000600e28 <_DYNAMIC>:
600e28:
01 00
add
%eax,(%rax)
600e2a:
00 00
add
%al,(%rax)
600e2c:
00 00
add
%al,(%rax)
600e2e:
00 00
add
%al,(%rax)
600e30:
01 00
add
%eax,(%rax)
600e32:
00 00
add
%al,(%rax)
600e34:
00 00
add
%al,(%rax)
600e36:
00 00
add
%al,(%rax)
600e38:
0c 00
or
$0x0,%al
600e3a:
00 00
add
%al,(%rax)
600e3c:
00 00
add
%al,(%rax)
600e3e:
00 00
add
%al,(%rax)
600e40:
a8 03
test
$0x3,%al
600e42:
40 00 00
add
%al,(%rax)
600e45:
00 00
add
%al,(%rax)
600e47:
00 0d 00 00 00 00
add
%cl,0x0(%rip)
# 600e4d <_DYNAMIC+0x25>
600e4d:
00 00
add
%al,(%rax)
600e4f:
00 d4
add
%dl,%ah
600e51:
05 40 00 00 00
add
$0x40,%eax
600e56:
00 00
add
%al,(%rax)
600e58:
19 00
sbb
%eax,(%rax)
600e5a:
00 00
add
%al,(%rax)
600e5c:
00 00
add
%al,(%rax)
600e5e:
00 00
add
%al,(%rax)
600e60:
10 0e
adc
%cl,(%rsi)
600e62:
60
(bad)
600e63:
00 00
add
%al,(%rax)
600e65:
00 00
add
%al,(%rax)
600e67:
00 1b
add
%bl,(%rbx)
600e69:
00 00
add
%al,(%rax)
600e6b:
00 00
add
%al,(%rax)
600e6d:
00 00
add
%al,(%rax)
600e6f:
00 08
add
%cl,(%rax)
600e71:
00 00
add
%al,(%rax)
600e73:
00 00
add
%al,(%rax)
600e75:
00 00
add
%al,(%rax)
600e77:
00 1a
add
%bl,(%rdx)
600e79:
00 00
add
%al,(%rax)
600e7b:
00 00
add
%al,(%rax)
600e7d:
00 00
add
%al,(%rax)
600e7f:
00 18
add
%bl,(%rax)
600e81:
0e
(bad)
600e82:
60
(bad)
600e83:
00 00
add
%al,(%rax)
600e85:
00 00
add
%al,(%rax)
600e87:
00 1c 00
add
%bl,(%rax,%rax,1)
600e8a:
00 00
add
%al,(%rax)
600e8c:
00 00
add
%al,(%rax)
600e8e:
00 00
add
%al,(%rax)
600e90:
08 00
or
%al,(%rax)
600e92:
00 00
add
%al,(%rax)
600e94:
00 00
add
%al,(%rax)
600e96:
00 00
add
%al,(%rax)
600e98:
f5
cmc
600e99:
fe
(bad)
600e9a:
ff 6f 00
ljmpq
*0x0(%rdi)
600e9d:
00 00
add
%al,(%rax)
600e9f:
00 98 02 40 00 00
add
%bl,0x4002(%rax)
600ea5:
00 00
add
%al,(%rax)
600ea7:
00 05 00 00 00 00
add
%al,0x0(%rip)
# 600ead <_DYNAMIC+0x85>
600ead:
00 00
add
%al,(%rax)
600eaf:
00 00
add
%al,(%rax)
600eb1:
03 40 00
add
0x0(%rax),%eax
600eb4:
00 00
add
%al,(%rax)
600eb6:
00 00
add
%al,(%rax)
600eb8:
06
(bad)
600eb9:
00 00
add
%al,(%rax)
600ebb:
00 00
add
%al,(%rax)
600ebd:
00 00
add
%al,(%rax)
600ebf:
00 b8 02 40 00 00
add
%bh,0x4002(%rax)
600ec5:
00 00
add
%al,(%rax)
600ec7:
00 0a
add
%cl,(%rdx)
600ec9:
00 00
add
%al,(%rax)
600ecb:
00 00
add
%al,(%rax)
600ecd:
00 00
add
%al,(%rax)
600ecf:
00 38
add
%bh,(%rax)
600ed1:
00 00
add
%al,(%rax)
600ed3:
00 00
add
%al,(%rax)
600ed5:
00 00
add
%al,(%rax)
600ed7:
00 0b
add
%cl,(%rbx)
600ed9:
00 00
add
%al,(%rax)
600edb:
00 00
add
%al,(%rax)
600edd:
00 00
add
%al,(%rax)
600edf:
00 18
add
%bl,(%rax)
600ee1:
00 00
add
%al,(%rax)
600ee3:
00 00
add
%al,(%rax)
600ee5:
00 00
add
%al,(%rax)
600ee7:
00 15 00 00 00 00
add
%dl,0x0(%rip)
# 600eed <_DYNAMIC+0xc5>
...
600ef5:
00 00
add
%al,(%rax)
600ef7:
00 03
add
%al,(%rbx)
...
600f01:
10 60 00
adc
%ah,0x0(%rax)
600f04:
00 00
add
%al,(%rax)
600f06:
00 00
add
%al,(%rax)
600f08:
02 00
add
(%rax),%al
600f0a:
00 00
add
%al,(%rax)
600f0c:
00 00
add
%al,(%rax)
600f0e:
00 00
add
%al,(%rax)
600f10:
30 00
xor
%al,(%rax)
600f12:
00 00
add
%al,(%rax)
600f14:
00 00
add
%al,(%rax)
600f16:
00 00
add
%al,(%rax)
600f18:
14 00
adc
$0x0,%al
600f1a:
00 00
add
%al,(%rax)
600f1c:
00 00
add
%al,(%rax)
600f1e:
00 00
add
%al,(%rax)
600f20:
07
(bad)
600f21:
00 00
add
%al,(%rax)
600f23:
00 00
add
%al,(%rax)
600f25:
00 00
add
%al,(%rax)
600f27:
00 17
add
%dl,(%rdi)
600f29:
00 00
add
%al,(%rax)
600f2b:
00 00
add
%al,(%rax)
600f2d:
00 00
add
%al,(%rax)
600f2f:
00 78 03
add
%bh,0x3(%rax)
600f32:
40 00 00
add
%al,(%rax)
600f35:
00 00
add
%al,(%rax)
600f37:
00 07
add
%al,(%rdi)
600f39:
00 00
add
%al,(%rax)
600f3b:
00 00
add
%al,(%rax)
600f3d:
00 00
add
%al,(%rax)
600f3f:
00 60 03
add
%ah,0x3(%rax)
600f42:
40 00 00
add
%al,(%rax)
600f45:
00 00
add
%al,(%rax)
600f47:
00 08
add
%cl,(%rax)
600f49:
00 00
add
%al,(%rax)
600f4b:
00 00
add
%al,(%rax)
600f4d:
00 00
add
%al,(%rax)
600f4f:
00 18
add
%bl,(%rax)
600f51:
00 00
add
%al,(%rax)
600f53:
00 00
add
%al,(%rax)
600f55:
00 00
add
%al,(%rax)
600f57:
00 09
add
%cl,(%rcx)
600f59:
00 00
add
%al,(%rax)
600f5b:
00 00
add
%al,(%rax)
600f5d:
00 00
add
%al,(%rax)
600f5f:
00 18
add
%bl,(%rax)
600f61:
00 00
add
%al,(%rax)
600f63:
00 00
add
%al,(%rax)
600f65:
00 00
add
%al,(%rax)
600f67:
00 fe
add
%bh,%dh
600f69:
ff
(bad)
600f6a:
ff 6f 00
ljmpq
*0x0(%rdi)
600f6d:
00 00
add
%al,(%rax)
600f6f:
00 40 03
add
%al,0x3(%rax)
600f72:
40 00 00
add
%al,(%rax)
600f75:
00 00
add
%al,(%rax)
600f77:
00 ff
add
%bh,%bh
600f79:
ff
(bad)
600f7a:
ff 6f 00
ljmpq
*0x0(%rdi)
600f7d:
00 00
add
%al,(%rax)
600f7f:
00 01
add
%al,(%rcx)
600f81:
00 00
add
%al,(%rax)
600f83:
00 00
add
%al,(%rax)
600f85:
00 00
add
%al,(%rax)
600f87:
00 f0
add
%dh,%al
600f89:
ff
(bad)
600f8a:
ff 6f 00
ljmpq
*0x0(%rdi)
600f8d:
00 00
add
%al,(%rax)
600f8f:
00 38
add
%bh,(%rax)
600f91:
03 40 00
add
0x0(%rax),%eax
...
Disassembly of section .got:
0000000000600ff8 <.got>:
...
Disassembly of section .got.plt:
0000000000601000 <_GLOBAL_OFFSET_TABLE_>:
601000:
28 0e
sub
%cl,(%rsi)
601002:
60
(bad)
...
601017:
00 e6
add
%ah,%dh
601019:
03 40 00
add
0x0(%rax),%eax
60101c:
00 00
add
%al,(%rax)
60101e:
00 00
add
%al,(%rax)
601020:
f6 03 40
testb
$0x40,(%rbx)
601023:
00 00
add
%al,(%rax)
601025:
00 00
add
%al,(%rax)
...
Disassembly of section .data:
0000000000601028 <__data_start>:
...
0000000000601030 <__dso_handle>:
...
Disassembly of section .bss:
0000000000601038 <__bss_start>:
...
Disassembly of section .comment:
0000000000000000 <.comment>:
0:
47
rex.RXB
1:
43
rex.XB
2:
43 3a 20
rex.XB cmp (%r8),%spl
5:
28 55 62
sub
%dl,0x62(%rbp)
8:
75 6e
jne
78 <_init-0x400330>
a:
74 75
je
81 <_init-0x400327>
c:
2f
(bad)
d:
4c 69 6e 61 72 6f 20
imul
$0x34206f72,0x61(%rsi),%r13
14:
34
15:
2e
cs
16:
37
(bad)
17:
2e 33 2d 31 75 62 75
xor
%cs:0x75627531(%rip),%ebp
# 7562754f <_end+0x7502650f>
1e:
6e
outsb
%ds:(%rsi),(%dx)
1f:
74 75
je
96 <_init-0x400312>
21:
31 29
xor
%ebp,(%rcx)
23:
20 34 2e
and
%dh,(%rsi,%rbp,1)
26:
37
(bad)
27:
2e 33 00
xor
%cs:(%rax),%eax

好家伙，这么几行简单的代码变成了这么一堆，看来连接器帮我们做了好多东西，我们不去管他，只挑其中我们自己写的部分来看。虽然at&t汇编和intel汇编格式不一样，但基本上是一一对应的，能够猜出究竟是在干什么。

00000000004004ec <sum>:
4004ec:
55
push
%rbp
4004ed:
48 89 e5
mov
%rsp,%rbp
4004f0:
48 83 ec 10
sub
$0x10,%rsp
4004f4:
89 7d fc
mov
%edi,-0x4(%rbp)
4004f7:
83 7d fc 01
cmpl
$0x1,-0x4(%rbp)
4004fb:
75 07
jne
400504 <sum+0x18>
4004fd:
b8 01 00 00 00
mov
$0x1,%eax
400502:
eb 12
jmp
400516 <sum+0x2a>
400504:
8b 45 fc
mov
-0x4(%rbp),%eax
400507:
83 e8 01
sub
$0x1,%eax
40050a:
89 c7
mov
%eax,%edi
40050c:
e8 db ff ff ff
callq
4004ec <sum>
400511:
8b 55 fc
mov
-0x4(%rbp),%edx
400514:
01 d0
add
%edx,%eax
400516:
c9
leaveq
400517:
c3
retq
0000000000400518 <main>:
400518:
55
push
%rbp
400519:
48 89 e5
mov
%rsp,%rbp
40051c:
48 83 ec 10
sub
$0x10,%rsp
400520:
c7 45 f8 05 00 00 00
movl
$0x5,-0x8(%rbp)
400527:
8b 45 f8
mov
-0x8(%rbp),%eax
40052a:
89 c7
mov
%eax,%edi
40052c:
e8 bb ff ff ff
callq
4004ec <sum>
400531:
89 45 fc
mov
%eax,-0x4(%rbp)
400534:
c9
leaveq
400535:
c3
retq
400536:
66 2e 0f 1f 84 00 00
nopw
%cs:0x0(%rax,%rax,1)
40053d:
00 00 00

一个sum函数，一个main函数。

main函数通过call sum的地址来调用sum函数，sum同样通过call这个地址来调用自身。

过程是一样的，我们就从sum函数还是分析。

每当进入调用函数的时候，被调用者首先push %rbp，mov %rsp to %rbp的方式来将调用栈的基地址保存起来。其中rbp，和rsp就是64位版本的ebp和esp。bp里面存放的当前栈的栈底，而sp存放当前栈的栈顶。刚进入一个新函数，需要把调用者的栈顶变成自己的栈底，于是就要把调用者的栈底地址保存起来，放在自己的栈底。这就是头两条指令的意义。注意一下顺序，push在前，说明当前的栈桢不包含调用者的基地址。

接下来sub $0x10,%rsp是做什么的呢？

从字面意义理解，这条指令的作用是将rsp减少了16字节,对于一个子长为8字节的64位系统来说，这就是两个字的大小。在x86平台上，栈生长的方向是倒生长，也就是说栈底在高地址，而栈顶则是底地址。（这个设计和小端字节序一样让人蛋疼）因此rsp减掉0x10就相当于把栈抬高了2个字。这两个字就是用来保存一些东西，但是现在还不知道该保存什么，所以先把这些空间保留出来。究竟这个空间是用来做什么的，过一会再解释。另外，这个操作解释了为什么c语言要声明变量类型，因为刚进入函数，程序的主体部分还没有运行的时候，编译器需要知道一共需要保留多大的空间。

再接下来的两条指令，先把edi寄存器的值放到比当前栈低高4的地方。再把它和0x1比较，根据我们的程序，可以猜到这里面放的就是变量n。edi寄存器里面保存的就是当前n的值需要注意的是，edi是一个32位寄存器，所以在我们这个64位的系统中，int类型的大小还是4个字节。而栈又是倒生长的，这个方法是没问题的，可以自行在脑中想象这时候栈的样子。紧贴栈底的是我们函数中定义的局部变量。不过我们申请了2个字的长度，栈中保留的空间还有12个字节。

接下来根据这个比较的结果选择跳转到400504的mov -0x4(%rbp),%eax这条指令上，或者是把eax-1并跳转到400516的leaveq这条指令的地址上。

leave的作用等同于move ebp to esp，pop ebp，也就是我们刚进入函数那两个操作的逆操作，把栈底变成栈顶，再上一个栈顶保存好的原来的ebp的值还原到ebp寄存器，完成了栈帧的切换。之后的return让程序跳转到调用之前的地址的下一个地址。这个地址在哪里？

了解一下ret的是怎么执行的。首先，在执行ret操作的时候，会先把下一个要执行的指令地址pop到ip寄存器里面，而这个地址就是函数调用者在调用函数之前，push进栈的。

这样，刚才保留的地址中，就又有一个是为call指令预留的函数返回后下一个要执行的地址。这个地址会占据8个字节。还有4个字节干什么去了？

因为我的机器是一个64位系统，字长为8字节，但是内存访问为了增加速度，都是采用字对齐的方式。剩下那4个字节，都是为了字对齐而浪费掉了。因此，在保留的空间中，局部变量之后保存的是要调用的函数的返回地址。

我们刚看到了函数返回的过程，再来看看另一个分支是怎样进行递归调用的。

首先，根据rbp访问到保存好的局部变量n,把它送到eax寄存器，再把eax-1于是这时候eax代表了n-1，再把eax送到edi，变成edi表示n-1，我开始递归，等到递归结束后，我们把当前n的值送到edx，再把eax和edx相加，结果送到eax。因为eax每次递归都会用到。假设我们再最后一次递归调用中，也就是n=1的时候，eax在相加之前等于0,edx=1.因此eax=eax+edx的意义就是1=1+0，也就是上一次递归的结果。再上一层就变成了eax=1+1=2，再上一层就是eax=2+1=3,以此类推，可以得到结论:

add %edx,%eax的意思就是f(n)=f(n-1)+n。其中，eax代表了下一层函数的返回值，而edx代表了这层函数的n。因为eax是全部递归的公用变量，而edx则是保存在当前栈中的。局部变量n，也就是-0x4(%rbp)的值是放在edi寄存器中传过来的，所以edi表示了当前函数的参数。十分精妙。

另外，函数参数除了通过寄存器传入，还可以通过堆栈传入。不同语言，不同系统，不同编译参数不一样。当前这种叫做fastcall调用。_cdecl和stdcall更为常见一些，对这些问题，我没什么研究，只是有点了解。

总之，假设参数不入栈，对于每次递归，消耗的空间至少有3个部分，局部变量,将要调用的函数的返回地址和当前栈帧的栈底的指针。对于这个sum函数来说，一共24个字节。

因为栈是倒生长的，而数组是正生长的。如果局部变量是一个数组，那么使劲向这个数组塞东西会毁掉上一个栈的内容，可以把返回地址所在的地方填成自己想要的地址。这就是缓冲区溢出的原理。以前的做法是把想要执行的代码的指令当成数据传进去，修改返回地址的指针，函数返回的时候就开始运行自己的指令。后来操作系统不让非代码段的程序运行，又针对这个对策有有新的办法。了解的不多，不过感觉挺好玩的