Question

Write, in Python, a recursive algorithm that takes, as input, a positive integer n, and returns, as output, the sum of the first n positive odd integers. Your solution should be recursive, and it should not contain any "for" loops or "while" loops.

Answer 1

Program code-

def sum_odds(n):
if n==1:
return 1
else:
return (2*n-1)+sum_odds(n-1)
  
print(sum_odds(8))

Explanation :

1. We define a function named sum_odds which accepts postive integer n.

2.if n is 1 , then we return 1 since first positive odd integer is 1.

3.if n is not 1 , say n is 8 . Then we return (2*n -1) which 2*8-1=15 and keep calling sum_odds(n-1) recursively

when n =8,

2*n-1=2*8-1=15 and call function sum_odds(n-1) which is sum_odds(7)

when  n =7

15 +  (2*n-1=2*7-1=13) and call function sum_odds(n-1) which is sum_odds(6)

when n =6

15 + 13+ (2*n-1=2*6-1=11) and call function sum_odds(n-1) which is sum_odds(5)

when n=5

15 + 13 + 11 + (2*n-1=2*5-1=9) and call function sum_odds(n-1) which is sum_odds(4)

when n=4

15 + 13 + 11 + 9 + (2*n-1=2*4-1=7) and call function sum_odds(n-1) which is sum_odds(3)

when n=3

15 + 13 + 11 + 9 + 7 + (2*n-1=2*3-1=5) and call function sum_odds(n-1) which is sum_odds(2)

when n=2

15 + 13 + 11 + 9 + 7 + 5 + (2*n-1=2*2-1=3) and call function sum_odds(n-1) which is sum_odds(1)

when n=1 , we return 1

Hence 15+13+11+9+7+5+3+1 = 64 is finally computed by the function and returned .