Recursion 1

递归和linkedlist

Fibonacci 引入

表象上 function calls itself
实质上 boil down a big problem to smaller ones (size n depends on n-1, n-2 ...)
实现上 - base case smallest problem to solve - recursive rule 当前层干一点什么事可以解决这个问题

Recursion解决问题的方式是做规约（reduction），把未知的规约到已知的。Recursion其实解决的更小号问题就是它本身。比如，实现一个从1加到n的function

class Solution(object):
  def fibonacci(self, K):
    """
    input: int K
    return: int
    """
    # write your solution here
    if K < 0:
      return 0

    if K == 0 or K == 1:
      return K
    
    return self.fibonacci(K-1)+self.fibonacci(K-2)

Time: \mathrm{O}\left(1+2+2^{2} +2^{3} +\ldots .+2^{n-1}\right)=\mathrm{O}\left(2^{n} \right) \\ Space: O(n)

常见错误

Recursive Function 的时间复杂度等于recursion tree节点的总个数？ ——除非每一个节点的operation是O(1)
Recursive Function 的时间复杂度等于最后一层节点的个数？ ——如果是一个直上直下一叉树就错得离谱了
Recursive Function 的时间复杂度等于最后一层节点的时间复杂度之和？ ——同上
Recursive Function 的空间复杂度等于recursion tree的层数或者高度？ ——除非每一层的space是O(1)
Recursive Function 的空间复杂度等于所有节点的空间复杂度之和？ ——只和直上直下的粉红色那条call stack有关，因为冯诺依曼原理，每一层调用结束之后原来的那个空间就被释放了

Call stack: can be regarded as a globally accessible information that tells you what happened before each break point in each level.

getSum 引入

iteratively

def getsum(n):
    acc=0
    for num in xrange (1,n+1):
        acc+=num
    return acc

recursively

$\begin{array}{l}{f(n)=f(n-1)+n} \\ {\begin{aligned} f(4) &=f(3)+4 \\ &=(f(2)+3)+4 \\ &=((f(1)+2)+3)+4 \end{aligned}}\end{array}$

def getsum(n):
    if n==1:
        return 1
    return n+getsum(n-1)

递归的调用带来一个新的execution environment（运行式环境）。

使用一次递归，其实本质上就是在实现一个数学归纳法induction的证明。

pow(a, b)

assumption: b>=0

class Solution(object):
  def power(self, a, b):
    """
    input: int a, int b
    return: long
    """
    # write your solution here
    if b==0:
      return 1
    elif b==1: #可以comment out 因为最后会到1
      return a

    midres = self.power(a, b//2)

    return midres*midres if b%2==0 else midres*midres*a

如果不存下midres，直接return两次，那么就多了很多重复计算。

现在的方法时间复杂度是O(logb)，空间复杂度是O(logb).

如果b<0, 要用1.0/a^(-b)

corner case

对于数值类型的题目，要想=0, >0, <0的情况

Linked List Recursion

Induction Base Verification (Base Case) P(0) and P(1)
Recursion Rule: Assuming k<n, P(k) is true. Generally, k=n-1. Focus on proving the correctness of P(n-1)-->P(n)

Print a singly linked list recursively

打印一个长度为n的链表，等价于以head为头和长度为n-1的链表

def PrintSinglyLinkedList(head):
    if head is None:
        return
        
    print head.value
    
    PrintSinglyLinkedList(head.next)

Search by Value

def search_by_value (head, value):
    if head is None:
        return None
    if head.value==value:
        return head
    return search_by_value (head.next, value)

Search by Index

Search by Value

Add to Index

Remove from Index to Recursion

Reverse a singly linked list

翻转后面的那些
让后面的node2指向自己 node2.next=head
让head.next=null
新的linkedlist的头也就是node n

时间、时间都是O(n)

def reverse (head): #reverse the linkedlist headed by head
    if head is None or head.next is None:
    # linked list is empty or contains only one node
        return head
    
    node = reverse(head.next)
    # 当前head的头节点就是所反转list的尾节点 在执行完head.next这一行之后，head.next的值还是原来的
    tail = head.next
    tal.next = head
    head.next = None 
    
    return node

Iterative vs Recursive Way

PreviousLinked List NextHashTable

Last updated 4 years ago