Introduction To Computer Science Past Paper PDF Fall 2024

INTRODUCTION TO COMPUTER SCIENCE 252-0032, 252-0047, 252-0058 Document authors: Manuela Fischer and Felix Friedrich Department of Computer Science, ETH Zurich Fall 2024 1 Recursion...

INTRODUCTION TO COMPUTER SCIENCE 252-0032, 252-0047, 252-0058 Document authors: Manuela Fischer and Felix Friedrich Department of Computer Science, ETH Zurich Fall 2024 1 Recursion 133 Section 11 Recursion Many mathematical functions are (or at least can be) naturally defined recursively, meaning that the function appears in its own definition. For instance, here is the recursive definition of the factorial:  1, if n ≤ 1 n! = (n − 1)! · n, otherwise The value of n! is defined in terms of the value of (n − 1)!. It is instructive to think about this definition as “If we already know the factorial (n − 1)!, then we can compute n! by multiplying (n − 1)! with n.” For instance, the value of 4! is defined as 3! · 4, where 3! is defined as 2! · 3, where 2! = 1! · 2 and 1! = 1. Putting this together, we get 4! = 3! · 4 = 2! · 3 · 4 = 1! · 2 · 3 · 4 = 1 · 2 · 3 · 4 = 24, the correct result! In C++, this works exactly the same: To compute the return value of fac(n), the program uses the return value of fac(n-1): // POST: return value is n! int fac(int n) { if (n