Wie stellt man die Gaußsche Summenformel rekursiv in c++ dar?

Hallo, eine Funktion soll die Summe zwischen 1 und einer vom Nutzer eingegebenen Zahl a rekursiv berechnen... also soll die Funktion ja mehrmals aufgerufen werden. Ich habe versucht die Gaußsche Summenformel so einzubringen.. wo ist mein Fehler?

    int rekursion(int a) {
               return (a*(rekursion(a+1))/2)

4 Antworten

Chroz192

12.06.2015, 02:21

Die Summenformel von Gauß ist ein geschlossener Ausdruck für die Summe der ersten n natürlichen Zahlen. Du brauchst, um so einen Ausdruck in einem Programm zu benutzen, keine Rekursion. Allerdings kannst du sehr wohl die Summe eplizit iterativ oder rekursiv-iterativ berechnen:

unsigned int summe_iterativ(unsigned int n)
{
    unsigned int sum = 0;
    for(int i = n; i > 0; i--)
        sum += i;
    return sum;
}
unsigned int summe_rekursiv(unsigned int n)
{
    return n > 1 ? n + summe_rekursiv(n-1) : 1;
}

Gruß

blackst0rm

12.06.2015, 03:15

Perfekte Antwort.

Youkakun

12.06.2015, 18:06

summe_rekursiv kann auch 0 erhalten, dann sollte nicht 1 sondern n (0/1) zurückgegeben werden.

i > 0 kann auf i verkürzt werden, denn der Wert 0 gilt bereits als unwahre Aussage und weniger kann es nicht werden.

unsigned alleinstehend gilt nach Standard bereits als int, man kann sich also etwas Schreibarbeit sparen ;)

Chroz192

21.06.2015, 15:47

@Youkakun

Der erste Einwand ist wohl berechtigt (man kann jedoch arugmentieren, dass 0 keine natürliche Zahl ist). Das zweite ist kein sauberer Stil, das wirst du in den wenigsten Projekten finden (man studiere hierzu einige C++ Projekte auf github). Bei Punkt drei kannst du mich erst überzeugen, wenn ich das entsprechende ISO/ANSI C++ Paper sehe, wobei ich denke, dass dies a priori nicht gilt.

Gruß

Roach5

11.06.2015, 22:59

Das was du gemacht hast ist ja eben nicht die Rekursionsformel sondern die geschlossene Form. In Rekursion sieht das ganze so aus:

int rekursion(int a)
{
  if(a == 1)
  {
    return 1;
  }
  return (a + rekursion(--a));
}

Youkakun

12.06.2015, 18:18

Und was, wenn ein Wert kleiner 1 übergeben wird? Du erlaubst sogar negative Zahlen und das ganze kann in einer Endlosrekursion enden.

Roach5

14.06.2015, 16:19

@Youkakun

Die Gaußsche Summe ist für n<1 undefiniert, somit muss hier nicht auf Fehler überprüft werden, wenn der Programmierer schlau genug ist, nur Werte zu übermitteln die auch mathematisch Sinn ergäben.

maximilianus7

Nutzer, der sehr aktiv auf gutefrage ist

im Thema programmieren

11.06.2015, 20:52

die formel hat mit rekursion nichts zu tun.

return (a*(a+1)/2);

genügt vollauf.

verreisterNutzer

11.06.2015, 21:21

Hallo!

... und bei einer Rekursion brauchst du eine Abbruchbedingung

Gruß

Hallo, also folgendes Problem: Die Summe von 1 bis zu einer vom Nutzer eingegebene Zahl soll einmal iterativ und rekursiv ausgegeben werden..

Für die iterative Funktion würde ich eine For-Schleife nehmen, aber wie soll ich das ausdrücken, dass alle Elemente dieser Schleife addiert werden sollen?

Das würde dann etwa so aussehen: func(int a) for(i=1;i<a;i++) {return ? (Summe aller i)}

Wie mache ich das?

...zur Frage

Java: Rekursion mit Array zwischenspeichern?

Betrachten Sie die rekursiv definierte Funktion Q.

Zur Berechnung von Q(n) für höhere n sollten Sie bereits berechnete Resultate in einem Array speichern, z.B. als statisches Attribut in ihrer Klasse. Ansonsten wird der naive Ansatz nicht terminieren.

Hat jemand einen Vorschlag, wie das mit dem Speichern des Zwischenergebnis in einem Array gehen soll?

Ich habe da mal einen Ansatz mit einer Hilfsmethode, aber irgendwie komme ich nicht ganz drauf.

Vielen Dank im Voraus.

Smokie

...zur Frage

Wie schreibt man eine Funktion, welche die Gaußsche Summenformel berechnet in Python?

...zur Frage

Array nach Wert prüfen rekrusiv (java)?

Hi sagen wir mal ich habe einen COde der so aussieht:

  public static int calculateBinomialCoefficient (int n, int k)
   {
      if (k == 1)
         return n;
      else if (n >= k && k == 0)
         return 1;
      else
       return (n * calculateBinomialCoefficient(n - 1, k - 1) / k);
 
   }
}

Nun hat mein Prof gemeint, dass die rekursion nicht linear ist und zu vielen gleichen Aufrufen mit gleichen Parameterkombis führt. EIne Möglichkeit damit das besser läuft ist es berechente Binomialkoeffizienten in einem zwei dimensionalen Array zu speichern und vor einem rekursiven Aufruf zu prüfen, ob die Lösung bereits 1x exisitert hat. EInen Array haben wir schon gegeben, mit der perfekten Länge.Dann habe ich mir das überlegt:

 public static int calculateBinomialCoefficient (int n, int k)
  {
   if (k == 1)
     return n;
   else if (n >= k && k == 0)
     return 1;
   else
for (int a=0; a<array.length;a++)
{
for (int b=0; b<array.length;b++)
{
if (array[a][b]==(n * calculateBinomialCoefficient(n - 1, k - 1) / k)
{
return array[a][b];
}else{
return (n * calculateBinomialCoefficient(n - 1, k - 1) / k);
if(array[a][b]==0){
array[a][b]==(n * calculateBinomialCoefficient(n - 1, k - 1) / k);
}
}
}
}
     
 
  }
}

(Ich hoffe kann man erkennen Tabs sind bisschen verrückt.)

Aber warum funktioniert das nun nicht? Habe doch alles beachtet oder?

...zur Frage

Binäre Suche: Iterativ vs rekursiv?

Ich habe beides in Java implementiert, verstehe aber nicht, warum die rekursive Variante mehr als doppelt so schnell ist. Müsste es normalerweise nicht anders herum sein? Oder habe ich bei der iterativen Variante irgendetwas suboptimal gelöst?

public static int binarySearchIterative(int[] a, int z) {
  int left = 0;
  int right = a.length - 1;

  while (left <= right) {
    int midpoint = (int)((left + right) / 2);

    if (z == a[midpoint]) {
      return midpoint;
    }

    if (z < a[midpoint]) {
      right = midpoint - 1;
    }
    else {
      left = midpoint + 1;
    }
  }

  return -1;
}

public static int binarySearchRecursive(int[] a, int z, int left, int right) {
  int midpoint = (int)((left + right) / 2);

  if (right < left) {
    return -1;
  }

  if (z == a[midpoint]) {
    return midpoint;
  }

  if (z < a[midpoint]) {
    return binarySearchRecursive(a, z, left, midpoint - 1);
  }
  else {
    return binarySearchRecursive(a, z, midpoint + 1, right);
  }
}

...zur Frage

Hilfe bei Java-Programm Binäre Suche (Rekursiv)?

Ich habe ein iteratives JavaProgrogramm zur Binären Suche erstellt, welches nun in eine rekursive Form gebracht werden soll.
Zudem sollen Testfälle vorbereitet werden, in denen min. 5 verschiedene Folgen F nach Schlüsseln gesucht werden kann. Eine Folge soll die Länge 1, eine weitere die Länge 2 haben, die restlichensollen länger als 10 Elemente sein. Nach dem Start des Programms soll die i-te Folge per Tastatureingabe ausgewählt und ein Suchschlüssel eingegeben werden. Anschließend soll das Programm die Indexposition ausgeben oder melden, dass der Schlüssel nichtgefunden wurde.

Hier das Programm in iterativer Form:

public class BinarySearch {

public static void main(String[] args) {
    new BinarySearch(); 
}

BinarySearch() {
    int[] f = {0, 1, 2, 4, 5, 8, 9, 12, 13, 18};
    int position = binarySearch(f, 5);
    System.out.println("Schlüsseln 5an Postition: "+ position);
}
int NO_KEY = -1;

int binarySearch(int[] f, int key){
    int i1 = 0, i2 = f.length - 1;
    while (i1 <= i2){
        int m = (i1 + i2) / 2;
        if ( key == f [m]) {
            return m;
        }else if (key < f[m]){
            i2= m - 1;
        }else {
            i1= m + 1;
        }
    }
    return NO_KEY;

} }

...zur Frage

Java / Palindrom rekursiv erkennen: Kann mir jemand sagen, wo in meinem Code der Fehler liegt?

Hallo,

ich habe eine Methode geschrieben, die mir true oder false liefert, falls der übergebene String ein Palindrom ist oder nicht. Da ich es rekursiv versuche, habe ich leider Schwierigkeiten.

Kann mir jemand sagen, wo der Fehler liegt? Danke schon mal!

public static void main(String[] args) {
  String s = "aknna";
  int length = s.length();

  System.out.println(isPalindrom(s, length));
}

public static boolean isPalindrom(String s, int length) {
  if (s.length() < 1) {
    return true;
  }

  if (s.charAt(0) != s.charAt((s.length() - 1))) {
    return false;
  }

  return isPalindrom(s, length - 1);
}

...zur Frage

C# | for-schleife als Rekursiv?

for (int i = 0; i < ziehungen; i++)
{
  for (int j = 0; j < wieviel; j++)
  {
    /* Neue Zahlen werden hier zufällig generiert */
    int neuezahlen = generator.Next(1, von + 1);

    /* Überprüfen ob eine Zahl bereits vorhanden ist -> Wenn ja wird eine neue gezogen */
    while (zahlen.Contains((neuezahlen)))
    {
      neuezahlen = generator.Next(1, von + 1);
    }

    zahlen[j] = neuezahlen;
  }

Hat jemand eine Idee, wie ich den bisherigen Code zu einem rekursiven Ablauf umschreiben kann? Ich würde das gerne ohne die for-Schleifen machen, habe aber noch nicht so viel Erfahrung, was die Rekursion betrifft.

...zur Frage

Java Rekursion mit Potenzzahlen?

public static void main(String[] args) {
		System.out.println(potenzRechner(4,3));
	}

	public static int potenzRechner(int potenzzahl1, int potenzzahl2) {
		
		if (potenzzahl2 == 0) {
			return 1;
		} else if (potenzzahl2 == 1) {
			return potenzzahl1;
		} else {
			return potenzzahl1 * potenzRechner(potenzzahl1, potenzzahl2 - 1);
		}
	}

Ich habe den Code oben mit einer Rekursiven Methode, der die Potenz der mitgegebenen Zahlen (in dem Fall 4 und 3) errechnet. Jedoch kann ich nicht 100% nachvollziehen was im letzten else Zweig passiert.

(return potenzzahl1 * potenzRechner(potenzzahl1, potenzzahl2 - 1);)

Wird Potenzzahl1 (4) nicht mit sich selbst (4) mal genommen, und das Potenzzahl2 (2) mal? Also 4 * 4 * 4 = 64? Und das solange bis Potenzzahl2 bei 1 ankommt. Also (4^3) 4 * 4 * 4 = 64, (4^2) 4 * 4 = 16, (4^1) 4 = 4. Oder verstehe ich was falsch? Dann sollte doch theoretisch das Ergebnis (64) beim ersten durchlauf schon rauskommen, für was dann eine Aufgabe bei der man das Rekursiv machen soll?

Zusammengefasst: Kann mir jemand auf gut Deutsch diesen Ausdruck, in der die Rekursion sattfindet, erklären?

...zur Frage

scanf wird ignoriert?

#include <stdio.h>

int main()
{
  int a;
  int error;
  printf("Geben sie eine Zahl ein: \n");

  do {
    error = scanf("%d", &a);
    printf("error: %d\tZahl:%d\n", error, a);
  }
  while (error == 0);

  return 0;
}

Die Schleife soll solange durchlaufen werden, bis eine Zahl eingegeben wurde.

Stattdessen wird scanf einfach nach dem ersten Durchlauf nicht mehr aufgerufen und man landet in einer Endlosschleife. Warum?

...zur Frage

Zweidimensionales Array wie rekursiv aufrufen?

Hallo,

ich habe ein zweidimensionales Array, bei der ich die BFS durchführen möchte,. Dabei möchte ich den anfangs übergebenen Graph, der als zweidimensionales Integerarray dargestellt ist( Java) im nächsten rekursiven Schritt so weitergeben als Parameter, dass quasi nur das zweidimensionale Array ohne den jeweils obersten Index bleibt, diesbezüglich möchte ich fragen, wie man das deklariert in Java.

danke im Voraus.

Anbei mein Quelltext:

public List<Integer> bfs(int[][] graph, int start) {
    List<Integer> result = new ArrayList<Integer>();
    if(!result.contains(start))
    {
    result.add(start);
    }
    int j=0;
    for(int i= 0; i<graph[j].length; i++)
    {
        if(!result.contains(graph[j][i]))
        {
            result.add(graph[j][i]);
        }
    ]
    bfs(graph[i][],start); // Hier soll der Graph erneut aufgerufen werden, nur ohne Index 0 , also 1 Zeile weniger 
    return result;
}

...zur Frage

Wie funktioniert Rekursion(Python)?

Ich versuche gerade zu verstehen, wie Rekursion funktioniert und bin dann auf die Fakultät gestoßen, die man ja rekursiv programmieren kann. Ich verstehe irgendwie nicht, wieso das überhaupt funktioniert, also ich kann dem Programm nicht wirklich folgen. Bei Iteration weiß ich genau was das Programm macht, aber bei Rekursion, weiß ich nicht mal wieso das funktioniert. Ich habe jetzt mal die Fakultätsfunktion programmiert:

def factorial(n):
    if n == 1:
        return 1
    else:
        b = nfactorial(n-1) print(b) return b

Das Programm gibt mir jetzt durch das "Print" so Zwischenergebnisse und ich kann nicht nachvollziehen, wieso es(z.B. bei Fak(4)) zuerst 12, dann12* 3 und erst zuletzt 1234 berechnet und nicht andersrum. Ich weiß, dass laut Definition Rekursion so funktioniert, also mit Rückeinsetzung, aber am Programm kann ich das nirgendwo erkennen.

...zur Frage

Java: Rekursion mit String-Methoden?

Hallo,

wir haben momentan das Thema Rekursion und dazu habe ich eine Frage.

private String wasTueIch(String wort) {
  if (wort.length() <= 1)
    return wort;
  else
    return wasTueIch(wort.substring(1, wort.length())) + wort.charAt(0);
}

Meine Frage ist, warum die Methode rekursiv ist und wie man einen Palindromtester (Palindrom: ein Wort, welches gespiegelt die gleiche Bedeutung hat) einbauen kann.

...zur Frage

Primzahlenerkennungsprogramm Python?

Hallo habe hier ein Programm mithilfe einer Funktion geschrieben,welche erkennen soll ob die eingegebene Zahl eine Primzahl ist.Allerdings kann ich das Unterprogramm nicht aufrufen weil eine Fehlermeldung kommt.Könntet ihr mir bitte helfen.

Mein Programm:

a = int(input("Zahl ? " )

def primzahl (a) :

for i in range (0,a):

if a == 1:

return False

elif a%i == 0 :

return False

else:

return True

primzahl(a)

...zur Frage

Was möchtest Du wissen?

Deine Frage stellen