CHAPTER 7: COMPUTATIONAL THINKING AND PROBLEM-SOLVING

7.1 RECURSION 

 7.1.1 Essential Features 

 Base Case: 

 

 Stopping condition 

 Prevents infinite recursion 

 

 Recursive Case: 

 

 Calls itself 

 Changes state toward base case 

 

 Unwinding: 

 

 When base case reached 

 Returns through call stack 

 Calculates final result 

 

 7.1.2 Advantages and Disadvantages 

 

 

 

 

 Advantages 

 Disadvantages 

 

 

 

 

 Simpler, more natural solutions 

 Less efficient (time and space) 

 

 

 Elegant for tree-like problems 

 Stack overflow risk 

 

 

 Reduced code complexity 

 Hard to debug 

 

 

 

 

 

 7.1.3 How Compilers Handle Recursion 

 Stack Usage: 

 

 Before call: Save current state (registers, local variables) onto stack 

 Make recursive call 

 During return: Restore state from stack 

 

 Unwinding: 

 

 When base case met 

 Values popped from stack in reverse order 

 Previous call states restored 

 

 7.1.4 Examples 

 Factorial: 

 

 <PYTHON> 

 

 

 

 

 

 

 

 

 

 def factorial ( n ): 

 

 

 if n <= 1 : 

 

 

 return 1 

 

 

 else : 

 

 

 return n * factorial(n- 1 ) 

 

 

 

 

 

 

 

 Fibonacci: 

 

 <PYTHON> 

 

 

 

 

 

 

 

 

 

 def fibonacci ( n ): 

 

 

 if n <= 1 : 

 

 

 return n 

 

 

 else : 

 

 

 return fibonacci(n- 1 ) + fibonacci(n- 2 ) 

 

 

 

 

 

 

 

 

 7.2 ALGORITHM COMPLEXITY 

 7.2.1 Big O Notation 

 

 

 

 

 Notation 

 Name 

 Example 

 

 

 

 

 O(1) 

 Constant 

 Array index access 

 

 

 O(log n) 

 Logarithmic 

 Binary search 

 

 

 O(n) 

 Linear 

 Linear search 

 

 

 O(n log n) 

 Linearithmic 

 Merge sort 

 

 

 O(n²) 

 Quadratic 

 Bubble sort 

 

 

 

 

 

 7.2.2 Comparing Algorithms 

 Time Complexity: 

 

 How execution time grows with input size 

 

 Space Complexity: 

 

 How memory usage grows with input size