What does this function do?

Question

Does this function means its calculating x=(x-1) + x^2?

Function unknown(x)
  if ( x == 1 )
    return 1
  else
    return unknown(x‐1) + x*x

Why is this tagged [array] and what language is it supposed to be? — JensG, Sep 06 '14 at 12:45
opps sorry. It's pseudocode. Once I know what is the function is doing, I will then know how to write it into C++/C#. — Zainu, Sep 06 '14 at 12:53
Have a look at this: http://programmers.stackexchange.com/questions/25052/in-plain-english-what-is-recursion — 11684, Sep 06 '14 at 12:54
[Sharing your research helps everyone](http://meta.programmers.stackexchange.com/questions/6559/why-is-research-important). Tell us what you've tried and why it didn’t meet your needs. This demonstrates that you’ve taken the time to try to help yourself, it saves us from reiterating obvious answers, and most of all it helps you get a more specific and relevant answer. Also see [ask] — gnat, Sep 06 '14 at 18:20

Rick Sanchez · Answer 1 · 2014-09-06T15:02:55.997

4

Well it recursively calculates x² + (x-1)² + (x-2)² + ⋯ + 2² + 1.

edited Sep 06 '14 at 15:02

answered Sep 06 '14 at 12:52

Rick Sanchez

149
6

score 2 · Answer 2 · answered Sep 06 '14 at 19:48

2

This is the sum of squares of natural numbers. The sum of first n natural numbers can be represented mathematically by:

n*(n+1)*(2n+1)/6

answered Sep 06 '14 at 19:48

Ankur Agarwal

121
2

score 2 · Accepted Answer · answered Sep 07 '14 at 00:41

The function can be written in a more mathematical form as:

unknown(1) = 1
unknown(x) = unknown(x - 1) + x * x    [if x is not 1]

To see why this is the same as the sum of squares, you can substitute the second line into itself recursively and observe the pattern that emerges:

unknown(x) =                                         unknown(x - 1) + x * x
unknown(x) =                     unknown(x - 2) + (x - 1) * (x - 1) + x * x
unknown(x) = unknown(x - 3) + (x - 2) * (x - 2) + (x - 1) * (x - 1) + x * x
etc ...

After expanding several times, you find that eventually* you will reach the special case of unknown(1) since the argument is steadily decreasing by one at each expansion. Hence,

(after expanding many times ...)
unknown(x) = unknown(1) + 2 * 2 + ... + (x - 1) * (x - 1) + x * x
unknown(x) =         1  + 2 * 2 + ... + (x - 1) * (x - 1) + x * x

Hence, this is simply the sum of squares.

[*] Unless your initial x is less than one, in which case the function diverges (never terminates) since the argument will just keep becoming more and more negative.

What does this function do?

3 Answers3