Concept

Concept#

The Three Laws/Axioms of Recursion#

Axiom 7 (The Three Laws of Recursion)

  1. A recursive algorithm must have a base case.

  2. A recursive algorithm must change its state and move toward the base case.

  3. A recursive algorithm must call itself, recursively.

Useful latex alignment.

\[\begin{split} \begin{align*} F_0+F_1+F_2+\cdots+F_n+F_{n+1} &=& \left(F_0+F_1+F_2+\cdots+F_n\right)+F_{n+1} \\ &=& \left(F_{n+2}-1\right)+F_{n+1} \\ &=& \left(F_{n+2}+F_{n+1}\right)-1 \\ &=& F_{n+3}-1 \tag*{(by assumption)} \end{align*} \end{split}\]

We start with the well-ordering principle: every nonempty set of positive integers contains a least element.

From this, we can prove the principle of mathematical induction. Suppose that \(P(n)\) is a property defined for every positive integer \(n\), and we want to prove that \(P(n)\) holds for all positive integers.

\textbf{Step 1:} We prove that \(P(1)\) is true.

\textbf{Step 2:} We assume that \(P(k)\) is true for some fixed positive integer \(k\), and use this assumption to prove that \(P(k+1)\) is also true.

Suppose, to the contrary, that there is at least one positive integer for which \(P(n)\) is false. Let \(S\) be the set of all positive integers for which \(P(n)\) is false, and by the well-ordering principle, \(S\) must have a smallest element, say \(m\).

By our induction hypothesis, \(P(1)\) is true, so \(m\) is not 1. Moreover, because \(m\) is the smallest counterexample, \(P(k)\) is true for all positive integers \(k\) less than \(m\). In particular, \(P(m-1)\) is true.

But, by the induction step, if \(P(m-1)\) is true, then \(P((m-1)+1)\) or \(P(m)\) is also true, a contradiction. Therefore, \(S\) must be empty, which implies that \(P(n)\) is true for all positive integers \(n\).

Time Complexity:

  • Amortized \(\mathcal{O}(1)\): This term is used to describe an algorithm’s average time taken per operation, over a worst-case sequence of operations. In the context of this problem, while the ‘pop’ operation may take \(\mathcal{O}(n)\) time in some cases (when stack s2 is empty and elements need to be moved from s1 to s2), most other operations take \(\mathcal{O}(1)\) time (when ‘pop’ is called while s2 has elements, or ‘push’/’peek’/’empty’ operations). So, when averaged over a large number of operations, the time complexity can be said to be \(\mathcal{O}(1)\).

  • Worst-case \(\mathcal{O}(n)\): This is the scenario where the operation takes the maximum time. In this problem, it happens when the ‘pop’ operation is called while stack s2 is empty and we need to move all the elements from s1 to s2. The time complexity for this single operation is \(\mathcal{O}(n)\), where n is the number of elements in the queue.

 1from typing import List
 2from rich.jupyter import print
 3
 4def list_sum(nums: List[int]) -> int:
 5    stack = []
 6    stack.append(nums)
 7
 8    result = 0
 9
10    while stack:
11        current = stack.pop()
12        # print(current)
13
14        # Base case: list is empty
15        if not current:
16            continue
17
18        # Recursive case: Split list into head and tail, add head to result, and push tail back onto the stack
19        head, *tail = current
20        result += head
21        print(tail)
22        stack.append(tail)
23
24    return result
25
26
27
28
29list_sum([1,3,5,7,9])

[3, 5, 7, 9]

[5, 7, 9]

[7, 9]

[9]

[]

25

References and Further Readings#