All lessonsOpen Open Open Open Open
5. Recursion
Recursion patterns
0 of 5 activities0%
Reading 1
Split the problem
Divide and conquer: split input, solve parts, merge (merge sort).
Multiple recursive calls: Fibonacci tree — exponential without memoization.
Memoization stores answers for overlapping subproblems — bridge to DP.
int fib(int n){
if(n<=1) return n;
return fib(n-1)+fib(n-2);
}Check 2
Naive fib
Naive recursive Fibonacci is
Fill in 3
Cache
Try it 4
Fib 6
Small n only.
main.cpp
Loading editor…
Output will appear here.
Assignment 5
Power of two recurse
Read n. Print yes if n is a power of two (n>=1), else no. (n & (n-1)) == 0 is fine.
main.cpp
Loading editor…