Recursion - Logic
Recursion is about defining a problem in terms of itself, breaking it down into smaller, more manageable pieces, and then combining the results to solve the original problem.
Merge Sort
The merge sort algorithm demonstrates the "divide and conquer" nature of recursion. It breaks down a large unsorted list into smaller sublists, sorts them, and then merges them back together.
Here is a step-by-step breakdown of how it works:
Base case: if the list has 1 or 0 element, it is already sorted, so no need to do anything.
Recursive case: if the list has more than one element, we split the list into two halves until it reaches the base case.
Merge: after the two halves are sorted, we combine them back together by comparing elements from both halves and putting them in the correct order.
PageRank
Google’s webpage ranking algorithm, aka PageRank, employs a recursive concept. Each page's importance is determined by the importance of the pages linking to it, creating a circular, self-referential system.
Mathematically, the rank R(P_i) of page P_i is defined as
where
B_i is the set of pages that link of P_i
R(P_j) is the rank of page P_j.
L(P_j) is the number of outbound links from page P_j
d is a damping factor that represents the probability of a user continuing to follow links and (1-d) represents the probability of randomly jumping to another page.
Note that the rank of page P_i is defined using the ranks of pages that link to page P_i. A recursion.
The Bellman Equation
The Bellman Equation is fundamental in dynamic programming and reinforcement learning. It embodies the recursive nature of decision-making: expresses the value of a current decision as a function of the immediate reward and the optimal future value, creating a chain of interdependent decisions.
Mathematically, the value of status s is defined as
where
a is an action you can take from state s.
R(s, a) is the immediate reward for taking action a in state s.
γ is a discount factor (between 0 and 1) which determines how much we value future rewards compared to immediate ones.
P(s’| s, a) is the probability of transiting to state s’ from state s by taking action a.
V(s’) is the value of the next state s’.
This means the value of the current state depends on the value of the next state. A recursion.
Conclusion
Recursion teaches us that sometimes the best way to understand a complex system is to look at how it relates to itself. If you have a problem that’s difficult to define, why not try to define it using itself?