Authored by Tony Feng

Created on April 2nd, 2022

Last Modified on April 2nd, 2022

Understanding Recursion

Intro

• Recursion is the process of defining a problem (or the solution to a problem) in terms of (a simpler version of) itself.
• Memoization could be used to save computational time.

Components of Recursion

• Base Case
  • The point where you stop applying the recursive case
• Recursive Steps
  • Divide the problem into one or more simpler or smaller parts of the problem;
  • Call the function (recursively) on each part;
  • Combine the solutions of the parts into a solution for the problem.

Characteristics

• Advantages of Recursion
  • Recursive functions make the code look clean and elegant.
  • A complex task can be broken down into simpler sub-problems using recursion.
  • Sequence generation is easier with recursion than using some nested iteration.
• Disadvantages of Recursion
  • Sometimes the logic behind recursion is hard to follow through.
  • Recursive calls are expensive (inefficient) as they take up a lot of memory and time.
  • Recursive functions are hard to debug.

Examples

The Factorial of an Integer

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

term = [0 for i in range(10)] # Memoization
# Fibonacci Series using memoized Recursion
def fib(n):
    # base case
    if n <= 1:
        return n

    # if fib(n) has already been computed we do not do further 
    # recursive calls and hence reduce the number of repeated work;
    # else store the computed value of fib(n) in an array term at
    # index n
    if term[n] != 0:
        return term[n]
    else:
        term[n] = fib(n - 1) + fib(n - 2)
        return term[n]

Leetcode 509 Fibonacci Number

1
2
3
4
5
6
7
8

# Time: O(N)
# Space: O(N) i.e. Recursive Stack
class Solution:
    def fib(self, n: int) -> int:
        if n <= 1:
            return n
        
        return self.fib(n - 1) + self.fib(n - 2)

Leetcode 206 Reverse Linked List

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]: 
        if not head or not head.next:
            return head

        node = self.reverseList(head.next)    
        head.next.next = head
        head.next = None
            
        return node

Reference

• 手把手带你刷Leetcode力扣 - 递归 Recursion
• 手把手带你刷Leetcode力扣 - 力扣509
• 手把手带你刷Leetcode力扣 - 力扣206
• Programiz - Python Recursion
• WTF is Memoization