πŸ–₯️
Berkeley CS61A: Notes
  • 🌍Hello, World!
  • πŸ’­Learn to Think Like Your Computer
  • Building Blocks
    • ❗Expressions in Python
      • ℹ️Mathematical Statements
      • 🀫Variables
      • πŸ‘Data Types in Python
    • 🚧Introduction to Functions
      • πŸƒβ€β™€οΈHow Python Executes a Function Call
      • 🚱Functions that Don't Return Anything
    • 🌊Control Flow
      • ⁉️What is an if statement?
      • πŸ’ΎWhat is a Loop?
      • 🚨What are Logical Operators?
        • πŸ˜–Logical Operators, Seemingly Illogical Behavior
      • 🚰How Does Control Flow?
    • ⚑Higher-Order Functions
      • ⏸️What are Higher-Order Functions Used For?
      • πŸ‘†Self-Reference
    • πŸ‘ΎEnvironments and Scope
      • πŸ–ŠοΈHow to Make Environment Diagrams
  • STRUCTURES OF DATA
    • ➰Recursion
      • πŸ«€Anatomy of Recursion
      • β›½Recursive Leap of Faith
    • πŸŽ„Tree Recursion
      • ⬇️The Use It/Lose It Principle
    • πŸ“€Iterables
      • βœ‚οΈList Slicing
      • πŸ’€Deep Lists
      • πŸŒ‹Iterable Functions
      • πŸ’½List Comprehensions
    • πŸ™ˆAbstraction
    • Trees
    • Linked Lists
    • Iterators and Generators
    • Efficiency
  • Extra Topics
    • 🎭Errors and their Types
      • 🏹Error vs Exception
      • πŸ”™What is Backtracing?
    • 🚑How the Terminal and the File are Different
    • 🍬Decorators
  • Debugging Tools
    • πŸ–¨οΈDebugging with Print Statements
    • πŸ›Debugging with the Debugger
Powered by GitBook
On this page

Was this helpful?

  1. STRUCTURES OF DATA
  2. Recursion

Recursive Leap of Faith

Jump Jump Jump!

Let's consider our factorial problem again:

def factorial(n):
    '''
    Accepts a non-negative number n and returns the factorial of that number.
    '''
    if n == 0:
        return 1
    else:
        return n * factorial(n-1)

Consider calculating factorial(150). Imagine writing the tree out for this the way we did for factorial(4) in the previous section. Go ahead and try it! You'll see that it gets absurdly big very fast.

Instead, we'll do something known as the recursive leap of faith. It goes like this: if we believe our base case is correct, that we'll reach our base case eventually, and that our recursive step is formatted properly, then we can assume that the recursive call will always return the correct value.

What this means is that, if our function works correctly, we can assume that the call factorial(149) returns to us the correct value. If it does so, we can multiply it with 150 to get factorial(150). This is the recursive leap of faith.

Taking the recursive leap of faith is one of the hardest things you'll have to do in this class. It requires you to believe that the code you wrote is correct... but you can often only write correct recursive code if you take the recursive leap of faith. A bit of a Catch-22. So, don't worry if you're not there yet! It takes time.

Over the next few sections, we'll go through recursive questions, see how they work behind the scenes, and in doing so, develop some faith in the recursive process.

PreviousAnatomy of RecursionNextTree Recursion

Last updated 3 years ago

Was this helpful?

➰
β›½