# Scheme反转链表

Scheme的正解版本只有一个，就是带复制TCO版本。

``````(define (reverse-tco ll rslt)
(if (eq? ll '())
rslt
(reverse-tco (cdr ll) (cons (car ll) rslt))))
``````

1. 递归比迭代好使。
2. 强制要求TCO。
3. cons操作起来非常方便。

# Python递归反转链表

``````def reverse_tco(ll, rslt):
if not ll:
return rslt
return reverse_tco(ll[1], [ll[0], rslt])
``````

# 递归转迭代

``````def reverse_iterate(ll):
rslt = None
while ll:
rslt, ll = [ll[0], rslt], ll[1]
return rslt
``````

``````def reverse_iterate(ll):
rslt = None
while ll:
rslt, ll[1], ll = ll, rslt, ll[1]
return rslt
``````

# Python非TCO版本

``````def reverse_recursion(ll):
if not ll[1]:
return ll
rslt = reverse_recursion(ll[1])
ll[1][1], ll[1] = ll, None
return rslt
``````

# 带环问题

``````t = [5, None]
ll = [1, [2, [3, [4, t]]]]
t[1] = ll[1][1]
``````

# Python解带环反转

``````def reverse_loop_tco(ll, rslt):
if not ll or ll[1] == PLACEHOLDER:
return rslt
ll[1], rslt, ll = PLACEHOLDER, [ll[0], rslt], ll[1]
return reverse_loop_tco(ll, rslt)
``````

``````def reverse_loop_iterate(ll):
rslt = None
while ll and ll[1] != PLACEHOLDER:
ll[1], rslt, ll = PLACEHOLDER, [ll[0], rslt], ll[1]
return rslt
``````

``````def reverse_loop_recursion(ll):
if not ll[1] or ll[1][1] == PLACEHOLDER:
return ll
t, ll[1] = ll[1], PLACEHOLDER
rslt = reverse_loop_recursion(t)
t[1], ll[1] = ll, None
return rslt
``````

# 编译/反汇编/调试/参数调用的基础知识

1. 要用O2编译，这个会启动优化。O1编译以下都不带这个优化。
2. 使用-g输出调试符号，方便gdb调试。
3. 不要strip，会干掉符号表，导致反汇编难度增大。
4. 使用objdump -d反汇编。
5. 使用gdb调试。

# C代码，O2优化及反汇编

``````struct node* reverse_tco(struct node *n, struct node *result)
{
struct node *t;
if (n == NULL) {
return result;
}
t = n->next;
n->next = result;
return reverse_tco(t, n);
}
``````

``````000000000000078b <reverse_tco>:
78b:   48 89 f0                mov    %rsi,%rax
78e:   48 85 ff                test   %rdi,%rdi
791:   74 18                   je     7ab <reverse_tco+0x20>
793:   48 83 ec 08             sub    \$0x8,%rsp
797:   48 89 fe                mov    %rdi,%rsi
79a:   48 8b 7f 08             mov    0x8(%rdi),%rdi
79e:   48 89 46 08             mov    %rax,0x8(%rsi)
7a2:   e8 e4 ff ff ff          callq  78b <reverse_tco>
7a7:   48 83 c4 08             add    \$0x8,%rsp
7ab:   f3 c3                   repz retq
``````

``````0000000000000850 <reverse_tco>:
850:   48 85 ff                test   %rdi,%rdi
853:   74 20                   je     875 <reverse_tco+0x25>
855:   48 89 f8                mov    %rdi,%rax
858:   eb 09                   jmp    863 <reverse_tco+0x13>
85a:   66 0f 1f 44 00 00       nopw   0x0(%rax,%rax,1)
860:   48 89 d0                mov    %rdx,%rax
863:   48 8b 50 08             mov    0x8(%rax),%rdx
867:   48 89 70 08             mov    %rsi,0x8(%rax)
86b:   48 89 c6                mov    %rax,%rsi
86e:   48 85 d2                test   %rdx,%rdx
871:   75 ed                   jne    860 <reverse_tco+0x10>
873:   f3 c3                   repz retq
875:   48 89 f0                mov    %rsi,%rax
878:   c3                      retq
879:   0f 1f 80 00 00 00 00    nopl   0x0(%rax)
``````

``````struct node* reverse_iterate(struct node *n)
{
struct node *t;
struct node *result = NULL;
while (n != NULL) {
t = n;
n = n->next;
t->next = result;
result = t;
}
return result;
}
``````

``````00000000000008c0 <reverse_iterate>:
8c0:   48 85 ff                test   %rdi,%rdi
8c3:   74 20                   je     8e5 <reverse_iterate+0x25>
8c5:   31 c9                   xor    %ecx,%ecx
8c7:   48 89 f8                mov    %rdi,%rax
8ca:   eb 07                   jmp    8d3 <reverse_iterate+0x13>
8cc:   0f 1f 40 00             nopl   0x0(%rax)
8d0:   48 89 d0                mov    %rdx,%rax
8d3:   48 8b 50 08             mov    0x8(%rax),%rdx
8d7:   48 89 48 08             mov    %rcx,0x8(%rax)
8db:   48 89 c1                mov    %rax,%rcx
8de:   48 85 d2                test   %rdx,%rdx
8e1:   75 ed                   jne    8d0 <reverse_iterate+0x10>
8e3:   f3 c3                   repz retq
8e5:   31 c0                   xor    %eax,%eax
8e7:   c3                      retq
8e8:   0f 1f 84 00 00 00 00    nopl   0x0(%rax,%rax,1)
8ef:   00
``````

# C反转链表，TCO版本，带环

C代码在这里。

``````struct node* reverse_loop_tco(struct node *n, struct node *result)
{
struct node *t;
struct node *n1;
if (n == NULL || n->next == &node_nil) {
return result;
}
n1 = (struct node*)malloc(sizeof (struct node));
n1->i = n->i;
n1->next = result;
t = n->next;
n->next = &node_nil;
return reverse_loop_tco(t, n1);
}
``````

# C反转链表，非TCO版本

``````struct node* reverse_recursion(struct node *n)
{
struct node *result = NULL;
if (n == NULL) {
return NULL;
}
if (n->next == NULL) {
return n;
}
/* result can be defined just in here */
result = reverse_recursion(n->next);
n->next->next = n;
n->next = NULL;
return result;
}
``````

O2反汇编后这样子：

``````0000000000000880 <reverse_recursion>:
880:   48 85 ff                test   %rdi,%rdi
883:   74 2b                   je     8b0 <reverse_recursion+0x30>
885:   53                      push   %rbx
886:   48 89 fb                mov    %rdi,%rbx
889:   48 8b 7f 08             mov    0x8(%rdi),%rdi
88d:   48 89 d8                mov    %rbx,%rax
890:   48 85 ff                test   %rdi,%rdi
893:   74 15                   je     8aa <reverse_recursion+0x2a>
895:   e8 e6 ff ff ff          callq  880 <reverse_recursion>
89a:   48 8b 53 08             mov    0x8(%rbx),%rdx
89e:   48 89 5a 08             mov    %rbx,0x8(%rdx)
8a2:   48 c7 43 08 00 00 00    movq   \$0x0,0x8(%rbx)
8a9:   00
8aa:   5b                      pop    %rbx
8ab:   c3                      retq
8ac:   0f 1f 40 00             nopl   0x0(%rax)
8b0:   31 c0                   xor    %eax,%eax
8b2:   c3                      retq
8b3:   0f 1f 00                nopl   (%rax)
8b6:   66 2e 0f 1f 84 00 00    nopw   %cs:0x0(%rax,%rax,1)
8bd:   00 00 00
``````

``````struct node* reverse_loop_recursion(struct node *n)
{
struct node *t;
struct node *result = NULL;
if (n == NULL) {
return NULL;
}
if (n->next == NULL || n->next->next == &node_nil) {
return n;
}
/* we had to keep t in stack. */
t = n->next;
n->next = &node_nil;
result = reverse_loop_recursion(t);
t->next = n;
n->next = NULL;
return result;
}
``````

``````0000000000000970 <reverse_loop_recursion>:
970:   48 85 ff                test   %rdi,%rdi
973:   74 53                   je     9c8 <reverse_loop_recursion+0x58>
975:   55                      push   %rbp
976:   53                      push   %rbx
977:   48 83 ec 08             sub    \$0x8,%rsp
97b:   48 8b 6f 08             mov    0x8(%rdi),%rbp
97f:   48 85 ed                test   %rbp,%rbp
982:   74 3c                   je     9c0 <reverse_loop_recursion+0x50>
984:   48 8d 15 b5 06 20 00    lea    0x2006b5(%rip),%rdx        # 201040 <node_nil>
98b:   48 39 55 08             cmp    %rdx,0x8(%rbp)
98f:   48 89 f8                mov    %rdi,%rax
992:   74 1b                   je     9af <reverse_loop_recursion+0x3f>
994:   48 89 fb                mov    %rdi,%rbx
997:   48 89 57 08             mov    %rdx,0x8(%rdi)
99b:   48 89 ef                mov    %rbp,%rdi
99e:   e8 cd ff ff ff          callq  970 <reverse_loop_recursion>
9a3:   48 89 5d 08             mov    %rbx,0x8(%rbp)
9a7:   48 c7 43 08 00 00 00    movq   \$0x0,0x8(%rbx)
9ae:   00
9af:   48 83 c4 08             add    \$0x8,%rsp
9b3:   5b                      pop    %rbx
9b4:   5d                      pop    %rbp
9b5:   c3                      retq
9b6:   66 2e 0f 1f 84 00 00    nopw   %cs:0x0(%rax,%rax,1)
9bd:   00 00 00
9c0:   48 89 f8                mov    %rdi,%rax
9c3:   eb ea                   jmp    9af <reverse_loop_recursion+0x3f>
9c5:   0f 1f 00                nopl   (%rax)
9c8:   31 c0                   xor    %eax,%eax
9ca:   c3                      retq
9cb:   0f 1f 44 00 00          nopl   0x0(%rax,%rax,1)
``````

# java实现fib

java版本很简单

``````public static int fib (int n) {
if (n <= 0) {
return 1;
}
return fib(n-1) + fib(n-2);
}
``````

`javap -v`输出byte code decompiler，结果如下：

``````     0: iload_0
1: ifgt          6
4: iconst_1
5: ireturn
7: iconst_1
8: isub
9: invokestatic  #2                  // Method fib:(I)I
13: iconst_2
14: isub
15: invokestatic  #2                  // Method fib:(I)I
19: ireturn
``````

# gcc对fib的优化

gcc让我觉得更加惊人的是对fib的优化。源码很简单，请直接看“附录D: 用C解fib的三种解法源码”，我们关键是看O2优化。

``````int fib0(int n)
{
if (n <= 0) {
return 1;
} else {
return fib0(n-1) + fib0(n-2);
}
}
``````

O2如下。

``````0000000000000720 <fib>:
720:   85 ff                   test   %edi,%edi
722:   7e 27                   jle    74b <fib+0x2b>
724:   55                      push   %rbp
725:   53                      push   %rbx
726:   31 ed                   xor    %ebp,%ebp
728:   89 fb                   mov    %edi,%ebx
72a:   48 83 ec 08             sub    \$0x8,%rsp
72e:   66 90                   xchg   %ax,%ax
730:   8d 7b ff                lea    -0x1(%rbx),%edi
733:   83 eb 02                sub    \$0x2,%ebx
736:   e8 e5 ff ff ff          callq  720 <fib>
73d:   85 db                   test   %ebx,%ebx
73f:   7f ef                   jg     730 <fib+0x10>
741:   48 83 c4 08             add    \$0x8,%rsp
745:   8d 45 01                lea    0x1(%rbp),%eax
748:   5b                      pop    %rbx
749:   5d                      pop    %rbp
74a:   c3                      retq
74b:   b8 01 00 00 00          mov    \$0x1,%eax
750:   c3                      retq
751:   0f 1f 44 00 00          nopl   0x0(%rax,%rax,1)
756:   66 2e 0f 1f 84 00 00    nopw   %cs:0x0(%rax,%rax,1)
75d:   00 00 00
``````

``````0000000000000760 <fib1>:
760:   55                      push   %rbp
761:   53                      push   %rbx
762:   48 83 ec 08             sub    \$0x8,%rsp
766:   85 ff                   test   %edi,%edi
768:   7e 26                   jle    790 <fib1+0x30>
76a:   89 fb                   mov    %edi,%ebx
76c:   31 ed                   xor    %ebp,%ebp
76e:   66 90                   xchg   %ax,%ax
770:   8d 7b ff                lea    -0x1(%rbx),%edi
773:   83 eb 02                sub    \$0x2,%ebx
776:   e8 e5 ff ff ff          callq  760 <fib1>
77d:   83 fb ff                cmp    \$0xffffffff,%ebx
780:   7d ee                   jge    770 <fib1+0x10>
782:   48 83 c4 08             add    \$0x8,%rsp
786:   89 e8                   mov    %ebp,%eax
788:   5b                      pop    %rbx
789:   5d                      pop    %rbp
78a:   c3                      retq
78b:   0f 1f 44 00 00          nopl   0x0(%rax,%rax,1)
790:   bd 01 00 00 00          mov    \$0x1,%ebp
795:   48 83 c4 08             add    \$0x8,%rsp
799:   89 e8                   mov    %ebp,%eax
79b:   5b                      pop    %rbx
79c:   5d                      pop    %rbp
79d:   c3                      retq
79e:   66 90                   xchg   %ax,%ax
``````

# 尾递归和转迭代关系

1. 退出条件在函数开头。这个条件可以被转换为一个退出判断函数test。
2. 以调用自身的地点为界，之前的函数叫f1，之后的函数叫f2。
3. 退出时可以将参数p转为另一个数据(例如恒定回复1)。这个转换参数叫final。

``````int foo(int n)
{
if (n <= 0) {
return 1;
}
return foo(n-1) << 1;
}
``````

O2反汇编

``````0000000000000770 <foo>:
770:   85 ff                   test   %edi,%edi
772:   7e 1c                   jle    790 <foo+0x20>
774:   48 83 ec 08             sub    \$0x8,%rsp
778:   83 ef 01                sub    \$0x1,%edi
77b:   e8 f0 ff ff ff          callq  770 <foo>
780:   48 83 c4 08             add    \$0x8,%rsp
786:   c3                      retq
787:   66 0f 1f 84 00 00 00    nopw   0x0(%rax,%rax,1)
78e:   00 00
790:   b8 01 00 00 00          mov    \$0x1,%eax
795:   c3                      retq
796:   66 2e 0f 1f 84 00 00    nopw   %cs:0x0(%rax,%rax,1)
79d:   00 00 00
``````

# 附录A：用Python解链表反向问题的六种解法源码

``````PLACEHOLDER = 'fix data'

def reverse_tco(ll, rslt):
if not ll:
return rslt
return reverse_tco(ll[1], [ll[0], rslt])

def reverse_loop_tco(ll, rslt):
if not ll or ll[1] == PLACEHOLDER:
return rslt
ll[1], rslt, ll = PLACEHOLDER, [ll[0], rslt], ll[1]
return reverse_loop_tco(ll, rslt)

def reverse_recursion(ll):
if not ll[1]:
return ll
rslt = reverse_recursion(ll[1])
ll[1][1], ll[1] = ll, None
return rslt

def reverse_loop_recursion(ll):
if not ll[1] or ll[1][1] == PLACEHOLDER:
return ll
t, ll[1] = ll[1], PLACEHOLDER
rslt = reverse_loop_recursion(t)
t[1], ll[1] = ll, None
return rslt

def reverse_iterate(ll):
rslt = None
while ll:
rslt, ll[1], ll = ll, rslt, ll[1]
return rslt

def reverse_loop_iterate(ll):
rslt = None
while ll and ll[1] != PLACEHOLDER:
ll[1], rslt, ll = PLACEHOLDER, [ll[0], rslt], ll[1]
return rslt

def main():
t = [5, None]
ll = [1, [2, [3, [4, t]]]]
t[1] = ll[1][1]
print(ll)
# rslt = reverse_tco(ll, None)
# rslt = reverse_recursion(ll)
# rslt = reverse_iterate(ll)
rslt = reverse_loop_tco(ll, None)
# rslt = reverse_loop_recursion(ll)
# rslt = reverse_loop_iterate(ll)
print(rslt)

if __name__ == '__main__':
main()
``````

# 附录B: 用C解链表反向问题的六种解法源码

``````#include <stdio.h>
#include <stdlib.h>

struct node {
int i;
struct node *next;
};

struct node node_nil = {-1, NULL};

int print_node(struct node *n, int depth)
{
if (n != NULL && depth != 0) {
printf("%i ", n->i);
print_node(n->next, depth-1);
} else {
printf("\n");
}
return 0;
}

struct node* reverse_tco(struct node *n, struct node *result)
{
struct node *t;
if (n == NULL) {
return result;
}
t = n->next;
n->next = result;
return reverse_tco(t, n);
}

struct node* reverse_recursion(struct node *n)
{
struct node *result = NULL;
if (n == NULL) {
return NULL;
}
if (n->next == NULL) {
return n;
}
/* result can be defined just in here */
result = reverse_recursion(n->next);
n->next->next = n;
n->next = NULL;
return result;
}

struct node* reverse_iterate(struct node *n)
{
struct node *t;
struct node *result = NULL;
while (n != NULL) {
t = n;
n = n->next;
t->next = result;
result = t;
}
return result;
}

struct node* reverse_loop_tco(struct node *n, struct node *result)
{
struct node *t;
struct node *n1;
if (n == NULL || n->next == &node_nil) {
return result;
}
n1 = (struct node*)malloc(sizeof (struct node));
n1->i = n->i;
n1->next = result;
t = n->next;
n->next = &node_nil;
return reverse_loop_tco(t, n1);
}

struct node* reverse_loop_recursion(struct node *n)
{
struct node *t;
struct node *result = NULL;
if (n == NULL) {
return NULL;
}
if (n->next == NULL || n->next->next == &node_nil) {
return n;
}
/* we had to keep t in stack. */
t = n->next;
n->next = &node_nil;
result = reverse_loop_recursion(t);
t->next = n;
n->next = NULL;
return result;
}

struct node* reverse_loop_iterate(struct node *n)
{
struct node *t;
struct node *result = NULL;
while (n != NULL && n->next != &node_nil) {
t = (struct node*)malloc(sizeof (struct node));
t->i = n->i;
t->next = result;
result = t;
t = n->next;
n->next = &node_nil;
n = t;
}
return result;
}

int main(int argc, char *argv[])
{
struct node node6 = {6, NULL};
struct node node5 = {5, &node6};
struct node node4 = {4, &node5};
struct node node3 = {3, &node4};
struct node node2 = {2, &node3};
struct node node1 = {1, &node2};
struct node *result;

/* node3.next = &node2; */

print_node(&node1, 7);
/* result = reverse_tco(&node1, NULL); */
/* result = reverse_recursion(&node1); */
/* result = reverse_iterate(&node1); */
result = reverse_loop_tco(&node1, NULL);
/* result = reverse_loop_recursion(&node1); */
/* result = reverse_loop_iterate(&node1); */
print_node(result, 7);
return 0;
}
``````

# 附录C: 用Scheme解链表反向问题的六种解法源码

``````(define placeholder "fix data")

(define (reverse-tco ll rslt)
(if (eq? ll '())
rslt
(reverse-tco (cdr ll) (cons (car ll) rslt))))

(define (reverse-loop-tco ll rslt)
(if (or (eq? ll '())
(eq? (cdr ll) placeholder))
rslt
(let ((t (cdr ll)))
(set-cdr! ll placeholder)
(reverse-loop-tco t (cons (car ll) rslt)))))

(define (reverse-recursion ll)
(cond
((eq? ll '()) '())
((eq? (cdr ll) '()) ll)
(else
(let ((rslt (reverse-recursion (cdr ll))))
(set-cdr! (cdr ll) ll)
(set-cdr! ll '())
rslt))))

(define (reverse-loop-recursion ll)
(cond
((eq? ll '()) '())
((or (eq? (cdr ll) '())
(eq? (cddr ll) placeholder))
ll)
(else
(let ((t (cdr ll)))
(set-cdr! ll placeholder)
(let ((rslt (reverse-loop-recursion t)))
(set-cdr! t ll)
(set-cdr! ll '())
rslt)))))

(define (reverse-iterate ll)
(let ((rslt '())
(t '()))
(while (not (eq? ll '()))
(set! t (cdr ll))
(set-cdr! ll rslt)
(set! rslt ll)
(set! ll t))
rslt))

(define (reverse-loop-iterate ll)
(let ((rslt '())
(t '()))
(while (and
(not (eq? ll '()))
(not (eq? (cdr ll) placeholder)))
(set! t (cdr ll))
(set-cdr! ll placeholder)
(set! rslt (cons (car ll) rslt))
(set! ll t))
rslt))

(define ll '(1 2 3 4 5 6))
(let
((t (cddr ll)))
(set-cdr! (cdddr t) t))
(display ll)
(newline)
;; (display (reverse-tco ll '()))
;; (display (reverse-recursion ll))
;; (display (reverse-iterate ll))
(display (reverse-loop-tco ll '()))
;; (display (reverse-loop-recursion ll))
;; (display (reverse-loop-iterate ll))
``````

# 附录D: 用C解fib的三种解法源码

``````int fib0(int n)
{
if (n <= 0) {
return 1;
} else {
return fib0(n-1) + fib0(n-2);
}
}

int fib1(int n)
{
int s;
if (n <= 0) {
return 1;
}
for (s = 0; n > -2; n-=2){
s += fib1(n-1);
}
return s;
}

int fib2(int n, int a, int b)
{
if (n == 0) {
return a;
}
return fib2(n-1, a+b, a);
}

int main(int argc, char *argv[])
{
int n = 20;
printf("fib0(%d): %d\n", n, fib0(n));
printf("fib1(%d): %d\n", n, fib1(n));
printf("fib2(%d): %d\n", n, fib2(n, 1, 1));
return 0;
}
``````

# 附录E: 用Python解决递归转迭代

``````def fib(n):
if n <= 0:
return 1
return fib(n-1)+fib(n-2)

def iterate(test, final, f1, f2, p):
i = 0
while not test(p):
p = f1(p)
i += 1
p = final(p)
while i != 0:
p = f2(p)
i -= 1
return p

def fib1(n):
p = [n, 1]

def test(p):
return p[0] <= 0

def final(p):
return p

def f1(p):
p[0] -= 1
return p

def f2(p):
p[1] += fib1(p[0]-1)
p[0] += 1
return p
return iterate(test, final, f1, f2, p)[1]

def foo(n):
def test(p):
return p <= 0

def final(p):
return 1

def f1(p):
return p-1

def f2(p):
return p << 1

return iterate(test, final, f1, f2, n)

def main():
print(fib(10))
print(fib1(10))
print(foo(3))

if __name__ == '__main__':
main()
``````