Rekurzija

Rekurzivno risanje: Roka riše roko, ki riše roko, ki...

Rekurzivna definicija

novi pojem = znani pojmi + novi pojem

rekurzivna definicija obsega 2 dela:

• robni pogoj

definira novi pojem pri robni vrednosti nove spremenljivke

novipojem(o) = znani pojem

• splošni primer

definira novi pojem tako, da uporabi znane pojme + novi pojem, vendar pri vrednostih rekurzijske spremenljivke, ki so manjše od tiste katero definiramo

novipojem(n) = znanipojem + novipojem(n')

n' < n

Naloge

Tukaj je nekaj zanimivih nalog za rešit če koga zanima.

1. Write a function to compute the sum of all numbers from 1 to n.
2. Write a function to compute 2 to the power of a non-negative integer.
3. Write a function to compute any number to the power of a non-negative integer.
4. Write a function to compute the nth Fibonacci number.
5. Write a function to compute the greatest common divisor (GCD) of two positive integers with Euclid's algorithm.
6. Write a function to compute GCD based on the following relations

   * GCD(2m, 2n) = 2 * GCD(m, n)
   * GCD(2m, 2n+1) = GCD(m, 2n+1)
   * GCD(2m+1, 2n+1) = GCD(n-m, 2m+1) if m < n
   * GCD(m, m) = m 

(after "ML for the Working Programmer", page 49).

1. Write a function to compute any number to the power of a positive integer using repeated squaring, that is, x2n = (xn)² and x2n+1 = x × x2n. (after "ML for the Working Programmer", pages 45 and 46).
2. Write a function to compute the integer square root of a non-negative integer using square_root(4x) = 2*square_root(x). (after "ML for the Working Programmer", pages 48 and 49)

Sorodni članki

• Rekurzija v prologu
• Hanojski stolpi
• Fakulteta