Quiz 8
Discrete Mathematics · 2 problems · solutions hidden, click to reveal
Flashcards
Problems
Give a recursive algorithm that, on input a nonnegative integer \(n\) and an integer \(x\), computes \(nx\) using only addition.
Show solution
Answer: f(n, x): if n = 0 return 0; else return x + f(n−1, x).
Use \(nx = x + (n-1)x\) with base case \(0\cdot x = 0\):
Func f(n, x):
if n = 0: return 0
else: return x + f(n-1, x)
Func f(n, x):
if n = 0: return 0
else: return x + f(n-1, x)
Trace this algorithm on \(n = 5\), where \(f(0)=0\) and \(f(n) = n^2 + f(n-1)\). Show all steps.
Show solution
Answer: \(f(5) = 55\).
\(f(0)=0\)
\(f(1)=1^2+f(0)=1\)
\(f(2)=2^2+f(1)=5\)
\(f(3)=3^2+f(2)=14\)
\(f(4)=4^2+f(3)=30\)
\(f(5)=5^2+f(4)=25+30=55\)
\(f(1)=1^2+f(0)=1\)
\(f(2)=2^2+f(1)=5\)
\(f(3)=3^2+f(2)=14\)
\(f(4)=4^2+f(3)=30\)
\(f(5)=5^2+f(4)=25+30=55\)