Rekursion är en process där en funktion anropar sig själv direkt eller indirekt. Rekursiva algoritmer används ofta inom datavetenskap för att lösa komplexa problem genom att dela upp dem i enklare.
Du kan bättre förstå rekursiva begrepp genom att lösa grundläggande programmeringsproblem som “produkten av två tal”, “summan av första n naturliga talen” och mer.
I den här artikeln får du lära dig hur du hittar summan av de första n naturliga talen med hjälp av rekursion.
Problembeskrivning
Du får ett naturligt tal n, måste du hitta summan av den första n naturliga tal med hjälp av rekursion.
Exempel 1: Låt n = 5
Därför är summan av de första 5 naturliga talen = 1 + 2 + 3 + 4 + 5 = 15.
Utgången är alltså 15.
Exempel 2: Låt n = 7
Därför är summan av de första 7 naturliga talen = 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28.
Utgången är alltså 28.
Exempel 3: Låt n = 6
Därför är summan av de första 6 naturliga talen = 1 + 2 + 3 + 4 + 5 + 6 = 21.
Utgången är alltså 21.
Rekursiv funktion för att hitta summan av de första N naturliga talen
De flesta rekursiva funktioner har följande relativa struktur:
FUNCTION name
IF condition THEN
RETURN result
ELSE
CALL FUNCTION name
END FUNCTION
För att hitta summan av de första n naturliga talen, observera och tillämpa följande pseudokod:
findSum(n):
IF n<=1 THEN
RETURN n
ELSE
RETURN n + findSum(n-1)
END FUNCTION
Nu kan du implementera denna pseudokod på ditt favoritspråk.
Notera: Du kan också hitta summan av de första n naturliga talen med följande matematiska formel:
Summan av n naturliga tal = n * (n + 1) / 2
Med denna metod kan du hitta summan i ett steg utan att använda rekursion.
C++-implementering för att hitta summan av första N naturliga tal med hjälp av rekursion
Nedan är C++-implementationen för att hitta summan av de första n naturliga talen med hjälp av rekursion:
// C++ implementation to find the sum of
// first n natural numbers using recursion
#include <iostream>
using namespace std;
// Recursive function to find the sum of first n natural numbers
int findSum(int n)
{
if (n<=1)
{
return n;
}
else
{
return n + findSum(n-1);
}
}
// Driver code
int main()
{
int n1 = 5, n2 = 7, n3 = 6;
cout << "n1: " << n1 << endl;
cout << "n2: " << n2 << endl;
cout << "n3: " << n3 << endl;
cout << "Sum of first " << n1 << " natural numbers: " << findSum(n1) << endl;
cout << "Sum of first " << n2 << " natural numbers: " << findSum(n2) << endl;
cout << "Sum of first " << n3 << " natural numbers: " << findSum(n3) << endl;
return 0;
}
Produktion:
n1: 5
n2: 7
n3: 6
Sum of first 5 natural numbers: 15
Sum of first 7 natural numbers: 28
Sum of first 6 natural numbers: 21
Python-implementering för att hitta summan av de första N naturliga talen med hjälp av rekursion
Nedan är Python-implementationen för att hitta summan av de första n naturliga talen med hjälp av rekursion:
# Python implementation to find the sum of
# first n natural numbers using recursion
# Recursive function to find the sum of first n natural numbers
def findSum(n):
if n<=1:
return n
else:
return n + findSum(n-1)
# Driver Code
n1 = 5
n2 = 7
n3 = 6
print("n1: ", n1)
print("n2: ", n2)
print("n3: ", n3)
print("Sum of first ", n1, " natural numbers: ", findSum(n1))
print("Sum of first ", n2, " natural numbers: ", findSum(n2))
print("Sum of first ", n3, " natural numbers: ", findSum(n3))
Produktion:
n1: 5
n2: 7
n3: 6
Sum of first 5 natural numbers: 15
Sum of first 7 natural numbers: 28
Sum of first 6 natural numbers: 21
C Implementering för att hitta summan av första N naturliga tal med hjälp av rekursion
Nedan är C-implementationen för att hitta summan av de första n naturliga talen med hjälp av rekursion:
// C implementation to find the sum of
// first n natural numbers using recursion
#include <stdio.h>
// Recursive function to find the sum of first n natural numbers
int findSum(int n)
{
if (n<=1)
{
return n;
}
else
{
return n + findSum(n-1);
}
}
// Driver code
int main()
{
int n1 = 5, n2 = 7, n3 = 6;
printf("n1: %d n", n1);
printf("n2: %d n", n2);
printf("n3: %d n", n3);
printf("Sum of first %d natural numbers: %d n", n1, findSum(n1));
printf("Sum of first %d natural numbers: %d n", n2, findSum(n2));
printf("Sum of first %d natural numbers: %d n", n3, findSum(n3));
return 0;
}
Produktion:
n1: 5
n2: 7
n3: 6
Sum of first 5 natural numbers: 15
Sum of first 7 natural numbers: 28
Sum of first 6 natural numbers: 21
JavaScript-implementering för att hitta summan av de första N naturliga talen med hjälp av rekursion
Nedan är JavaScript-implementeringen för att hitta summan av de första n naturliga talen med hjälp av rekursion:
// JavaScript implementation to find the sum of
// first n natural numbers using recursion
// Recursive function to find the sum of first n natural numbers
function findSum(n) {
if (n<=1) {
return n;
} else {
return n + findSum(n-1);
}
}// Driver Code
var n1 = 5, n2 = 7, n3 = 6;
document.write("n1: " + n1 + "<br>");
document.write("n2: " + n2 + "<br>");
document.write("n3: " + n3 + "<br>");
document.write("Sum of first " + n1 + " natural numbers: " + findSum(n1) + "<br>");
document.write("Sum of first " + n2 + " natural numbers: " + findSum(n2) + "<br>");
document.write("Sum of first " + n3 + " natural numbers: " + findSum(n3) + "<br>");
Produktion:
n1: 5
n2: 7
n3: 6
Sum of first 5 natural numbers: 15
Sum of first 7 natural numbers: 28
Sum of first 6 natural numbers: 21
Java-implementering för att hitta summan av första N naturliga tal med hjälp av rekursion
Nedan är Java-implementeringen för att hitta summan av de första n naturliga talen med hjälp av rekursion:
// Java implementation to find the sum of
// first n natural numbers using recursion
public class Main
{
// Recursive function to find the sum of first n natural numbers
public static int findSum(int n)
{
if (n <= 1)
{
return n;
}
else
{
return n + findSum(n - 1);
}
}
// Driver code
public static void main(String[] args)
{
int n1 = 5, n2 = 7, n3 = 6;
System.out.println("n1: " + n1);
System.out.println("n2: " + n2);
System.out.println("n3: " + n3);
System.out.println("Sum of first " + n1 + " natural numbers: " + findSum(n1));
System.out.println("Sum of first " + n2 + " natural numbers: " + findSum(n2));
System.out.println("Sum of first " + n3 + " natural numbers: " + findSum(n3));
}
}
Produktion:
n1: 5
n2: 7
n3: 6
Sum of first 5 natural numbers: 15
Sum of first 7 natural numbers: 28
Sum of first 6 natural numbers: 21
Lär dig mer om rekursion
Rekursivt tänkande är mycket viktigt i programmering. Ibland kan den rekursiva lösningen vara enklare att läsa än den iterativa. Du kan lösa många problem som Tower of Hanoi Problem, DFS of Graph, Inorder/Preorder/Postorder Tree Traversals, etc., med hjälp av rekursion.
Rekursion är en mycket kraftfull problemlösningsstrategi. Numera används det också flitigt i funktionell programmering. Du måste känna till grunderna för rekursion och hur du kan tillämpa den i dina programmeringssträvanden.
Om författaren
Yuvraj Chandra (80 artiklar publicerade)
Yuvraj är en datavetenskapsstudent vid University of Delhi, Indien. Han brinner för Full Stack Web Development. När han inte skriver undersöker han djupet i olika teknologier.
Mer från Yuvraj Chandra
Prenumerera på vårt nyhetsbrev
Gå med i vårt nyhetsbrev för tekniska tips, recensioner, free e-böcker och exklusiva erbjudanden!
Klicka här för att prenumerera
