b.stefanuk.ca

Appearance

Recursive code is conceptually difficult when first encountering it, especially for more complex problems. The truth is, recursive programming isn't intuitive because it requires faithful abstract thinking. Working through each step of a recursive problem often makes the solution more confusing, so don't do it, trust yourself and test the functionality.

The essential problem of recursion is to solve a sub-problem with itself

Tip
  1. It is essential to modify the input passed to your recursive calls.
  2. Think of the recursive calls like a growing pyramid. They won't return until the terminating case is found at which point they will all return at once.
  3. You may need mutiple terminating cases if your recursion relies on multiple terms (e.g. the famous Fibonacci problem)

Steps to solving recursive problems:

  1. Understand what your function is is trying to achieve.
    • Place a doc-comment with your function describing describing the task.
  2. Pick a sub-problem that manipulates the input and assume your function works.
    • The trick here is to understand the ways in which your data can be altered when being passed to the next level of recursion. For integers it may be n-1 for string is may be s[1:]
  3. Back-solve the problem given a specific input to the original and subproblem.
    python
    fibonacci(5) = 5 # Original
fibonacci(4) = 3 # Sub-problem
# Back-solve
fibonacci(4) + fibonacci(3) = 5
# Implies
fibonacci(n) = fibonnaci(n-1) + fibonacci(n-2)
    fibonacci(5) = 5 # Original
fibonacci(4) = 3 # Sub-problem
# Back-solve
fibonacci(4) + fibonacci(3) = 5
# Implies
fibonacci(n) = fibonnaci(n-1) + fibonacci(n-2)
4. Add a terminating base case.
	- Typically an `if else` statement in the beginning of your function.
	- The trick is to find a trivial input such that if were entered no recursive calls would be made.

> [!Tip]
4. Add a terminating base case.
	- Typically an `if else` statement in the beginning of your function.
	- The trick is to find a trivial input such that if were entered no recursive calls would be made.

> [!Tip]