Sum of the series 1^1 + 2^2 + 3^3 + ….. + n^n using recursion
Given an integer n, the task is to find the sum of the series 11 + 22 + 33 + ….. + nn using recursion.
Examples:
Input: n = 2
Output: 5
11 + 22 = 1 + 4 = 5Input: n = 3
Output: 32
11 + 22 + 33 = 1 + 4 + 27 = 32
Approach: Starting from n, start adding all the terms of the series one by one with the value of n getting decremented by 1 in each recursive call until the value of n = 1 for which return 1 as 11 = 1.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach #include <bits/stdc++.h> using namespace std; #define ll long long int // Recursive function to return // the sum of the given series ll sum( int n) { // 1^1 = 1 if (n == 1) return 1; else // Recursive call return ((ll) pow (n, n) + sum(n - 1)); } // Driver code int main() { int n = 2; cout << sum(n); return 0; } |
Java
// Java implementation of the approach class GFG { // Recursive function to return // the sum of the given series static long sum( int n) { // 1^1 = 1 if (n == 1 ) return 1 ; else // Recursive call return (( long )Math.pow(n, n) + sum(n - 1 )); } // Driver code public static void main(String args[]) { int n = 2 ; System.out.println(sum(n)); } } |
Python3
# Python3 implementation of the approach # Recursive function to return # the sum of the given series def sum (n): if n = = 1 : return 1 else : # Recursive call return pow (n, n) + sum (n - 1 ) # Driver code n = 2 print ( sum (n)) # This code is contributed # by Shrikant13 |
C#
// C# implementation of the approach using System; class GFG { // Recursive function to return // the sum of the given series static long sum( int n) { // 1^1 = 1 if (n == 1) return 1; else // Recursive call return (( long )Math.Pow(n, n) + sum(n - 1)); } // Driver code public static void Main() { int n = 2; Console.Write(sum(n)); } } |
PHP
<?php // PHP implementation of the approach // Recursive function to return // the sum of the given series function sum( $n ) { // 1^1 = 1 if ( $n == 1) return 1; else // Recursive call return (pow( $n , $n ) + sum( $n - 1)); } // Driver code $n = 2; echo (sum( $n )); // This code is contributed // by Code_Mech ?> |
Javascript
<script> // Javascript implementation of the approach // Recursive function to return // the sum of the given series function sum(n) { // 1^1 = 1 if (n == 1) return 1; else // Recursive call return (Math.pow(n, n) + sum(n - 1)); } // Driver code var n = 2; document.write(sum(n)); // This code is contributed by rutvik_56. </script> |
Output:
5
Time Complexity: O(nlogn), for using pow function for numbers 1 till N.
Auxiliary Space: O(n) for recursive stack space.