FirstHack Learn
Log in Sign up free
Lessons in this course 0/6 All courses Algorithms and Complexity

CSE

Progress0 / 6 lessons
  1. 1. Big-O without hand-waving
  2. 2. Searching: linear and binary
  3. 3. Bubble, selection and insertion sort
  4. 4. Merge sort and quick sort
  5. 5. Recursion and how to reason about it
  6. 6. Greedy versus dynamic programming

Courses › Algorithms and Complexity

Recursion and how to reason about it

Base case, recursive case, the call stack, and why naive Fibonacci is catastrophically slow.

12 min read · Lesson 5 of 6 · Pro

Stop tracing, start trusting

Most students try to understand recursion by tracing every call on paper. That works for depth 3 and collapses at depth 10. It is the wrong tool.

The right method has three steps.

  1. Write the base case. The input so small the answer is obvious.
  2. Assume the function already works for any smaller input. Do not

justify this. Assume it.

  1. Use that assumption to solve the current input, and make sure your

recursive call is on something strictly smaller.

If all three hold, the function is correct. This is induction, the same proof technique from your discrete mathematics paper.

Applying the method

Sum of an array.

The rest of this lesson is Pro

The free lessons of Algorithms and Complexity finish what they start — read those first if you have not. This one goes further, and it is part of the paid half.

A pass opens the paid lessons of every course, the mock test papers and the company-wise series. It ends on its own date; nothing renews by itself.

Get a pass — from ₹29 for 7 days

Already bought one? Log in.