What is it about?⌗

Series in mathematics are fascinating. Some series converge to a value, and other series diverge. According to a story about the mathematician Gauss, his teacher gave the class the task to calculate the sum $1 + 2 + 3 + … + 100$. The teacher prepared himself to relax while the pupils struggled with the task. Gauss found a mathod to calculate such a sum instantly, and gave the teacher no rest.

Well, let’s examing that sum like

S1 = 1
S2 = 1 + 2
S3 = 1 + 2 + 3
...

or better:

S100 = 100 + 99 + 98 + ... + 1
 S99 =  99 + 98 + 97 + ... + 1
 ...
  S1 = 1

or even better:

S100 = 100 + S99
 S99 =  99 + S98
 ...
  S1 = 1

or in general:

S(n) = n + S(n-1)
S(1) = 1

The last approach may serve as a model for the recursive function implementation in (e.g) Python. Here is the code:

def sum(val):
   if val == 1:
      return 1 # Yes, this is the last row in our approach above
   else:
      return val + sum(val - 1)

print(sum(100))

The output: $5\,050$, the number Gauss calculated in minutes.

I think recursion is like magic, we add (or any other operation) something not yet calculated. The result is obtained when the program reaches the start condition (or end condition?).

Well, there are plenty of series waiting to be calculated. Another example is the alternating harmonic series: $$1-\frac{1}{2}+\frac{1}{3}-\frac{1}{4}+…$$ Believe it or not, this series equals the irrational number $\ln 2$, that is, the natural logaritm of 2. It’s a bit harder to implement it as a recursion due to the alternation och signs between the terms. I will handle it with the modulo operator, % in Python:

import math as m # For reference value
def ln2(val):
   if val == 1: 
       return 1
   else:
      return 1/val + (-1**(val % 2)) * ln2(val - 1) # ** means powered to

for n in [11, 31, 51, 71, 91, 191, 291, 391]:
	print(f"S{n} = {ln2(n):.8f}")
	
print(f"\nReference: ln(2) ≈ {m.log(2):.8f}")

Here is the sum the first n terms with some different values of n:

S11  = 0.73654401
S31  = 0.70901620
S51  = 0.70285500
S71  = 0.70013985
S91  = 0.69861150
S191 = 0.69575813
S291 = 0.69486244
S391 = 0.69442432

Reference: ln(2) ≈ 0.69314718

I have choosen some odd values for the sequence number. In this implemantation the program goes through the sequence from the higher to the lower ordinals. In order to get the + and - signs in right places we have to do so as a quick and dirty fix 😅.

We see that the series converges really slow, 391 terms just give us 2 correct decimals. It seems that the default maximum recursion depth is 995, and this number of terms gives us 0.69364944. A little bit closer. We may increase the maximum recursion depth with sys.setrecursionlimit(), but I think there are good reasons not to do.

As I said, I’m fascinated about recursion and recursive functions. Nevertheless, in some cases there are strong reasons to use recursion in programming for simplifying tasks as well as there are situations there recursion should be avoided.

Some references⌗