Grade 10 · 12 algorithmsCitește în română

RecursionRecursivitate

Every recursion algorithm from the Romanian high school curriculum, with the idea explained, its complexity, examples and code you can edit and run right here.

Create a free account Browse the collection

12algorithms
6chapters
1grade

Recursion

Recursivitate · 12 algorithms

Printing the digits in order, recursivelyAfișarea cifrelor în ordine, recursivWhere we print relative to the recursive call matters. In inOrdine we print AFTER the recursive call: first the call for n / 10 finishes (printing…O(n)
Recursive GCDCmmdc recursivEuclid's algorithm written recursively: gcd(a, 0) = a, and gcd(a, b) = gcd(b, a % b). The recursive call is the last operation in the function (tail…O(log n)
Converting to base 2, recursivelyConversia în baza 2, recursivWhen converting by repeated division by 2, the remainders come out in the reverse of the order they must be written in. Recursion solves this by…O(log n)
Recursive factorialFactorial recursivThe mathematical definition is already recursive: 0! = 1 and n! = n * (n - 1)!. The function has a stopping condition (n == 0) and a recursive call…O(n)
Recursive FibonacciFibonacci recursivThe Fibonacci sequence: F(0) = 0, F(1) = 1, F(n) = F(n - 1) + F(n - 2). The direct translation has two recursive calls, so the call tree almost…Exponential
The Ackermann functionFuncția AckermannThe Ackermann function has two arguments: A(0, n) = n + 1; A(m, 0) = A(m - 1, 1); A(m, n) = A(m - 1, A(m, n - 1)). Its values grow extremely fast…Exponential
The Manna-Pnueli functionFuncția Manna-PnueliThe function is defined as: f(x) = x - 1 if x >= 12, otherwise f(x) = f(f(x + 2)). The inner call f(x + 2) is computed first, and its result becomes…O(n)
Reversing a string, recursivelyInversarea unui șir de caractere, recursivThe function inverseaza(s, i) handles the characters from position i to the end. If s[i] is not '\0', it first calls itself for the rest of the…O(n)
Number of occurrences in an array, recursivelyNumărul de apariții într-un vector, recursivThe number of occurrences of x among the first n elements is the number of occurrences among the first n - 1 elements, plus 1 if the last element…O(n)
Recursive palindrome checkPalindrom recursivA word is a palindrome if its first and last characters are equal and what remains between them is also a palindrome. The function palindrom(s, st,…O(n)
Power of a number, recursivelyPuterea unui număr, recursivThe direct version uses a^n = a * a^(n - 1) and makes n calls. The fast version halves the exponent: if n is even, a^n = (a^(n/2))^2, otherwise a^n…O(n)
Sum of digits, recursivelySuma cifrelor, recursivThe digit sum of n is its last digit (n % 10) plus the digit sum of the number left after cutting it off (n / 10). Stop: a one-digit number (n < 10)…O(n)