Which of these expressions could replace a call to this function?

Question

Consider the recursive function,
```
int rec(int n)
{
if (1 ==n )
return 1;
else
return rec(n-1) + 2*n - 1;
}
```

a) n2 - 1
b) n2 + 1
c) n2
d) (n + 1)2
e) (n - 1)2

Answer 1

c) n2

If you look at the carefully, you may see that it this sums successive odd numbers. The sum of k odd numbers sums to k2. Otherwise, you could execute this for a few values of argument, n, say 1, 2, 3, and 4, and unroll the recursion. You will find that rec(n) sums successive odd numbers.