递归函数的宏观语义
来源：2-9 链表添加元素递归方法的常见问题解析
努力做学霸123
2021-11-14 15:18:37
bobo老师你好，请问一下，在下面的截图中红框框那部分，这个递归函数 private Node add(Node, node, Int index, E e)这个递归函数的宏观语义是你在ppt里的注释:在以node为头节点的链表index位置插入元素e 吗? 如果是的话 递归终止条件站在宏观语义的角度怎么解释呢？ 在以node为头节点的链表index为0位置插入元素e？在宏观语义的角度上，为什么index为0就该插入了呢？我将这个终止条件的语义和整个递归的宏观语义联系不起来。想不通站在宏观语义的角度该怎么解释递归终止的这种情况。您能帮忙解释一下吗？
相关截图：
1回答
-
1）
宏观语义的解读是对的：在以node为头节点的链表index位置插入元素e
2）
当 index = 0 的时候，表示在以 node 为头结点的链表前头，插入一个新的节点（即新的节点的 index 为 0）。那么我们只需要 new Node(e, node) 就好。
注意，这里在构造函数中隐含了新建的节点的 next 是 node。你也可以理解成以下的三句话：
Node newNode = new Node(e);
newNode.next = node;
return newNode;
3）
如果 index 不为 0 的话，在以node为头节点的链表index位置插入元素e，相当于要以 node->next 为头结点的链表的 index - 1 位置插入元素 e，所以就递归下去了。
随便举一个例子：
1 -> 2 -> 3 -> 4 -> 5 -> null
在这个链表中 index = 3 的位置插入元素 666
即在以 1 为头节点，index = 3 的位置插入元素 666；
即在以 2 为头节点，index = 2 的位置插入元素 666；
即在以 3 为头节点，index = 1 的位置插入元素 666；
即在以 4 为头节点，index = 0 的位置插入元素 666；
可以插入了，插入结果是 666 -> 4 -> 5 -> null
插入结果返回上一层，结果是 3 -> 666 -> 4 -> 5 -> null
返回上一层，结果是 2 -> 3 -> 666 -> 4 -> 5 -> null
返回上一层，结果是 1 -> 2 -> 3 -> 666 -> 4 -> 5 -> null
结束。
继续加油！：）
1
相似问题