Funkcje rekurencyjne — część 2

Każda funkcja rekurencyjna składa się z tych samych dwóch części:

1. Przypadek bazowy określa, kiedy należy się zatrzymać.
2. Krok rekurencyjny wywołuje funkcję z mniejszym argumentem.

Silnia z n to n * (n - 1) * ... * 1, więc silnia z n to n razy silnia z n - 1:

func factorial(n: int) -> int:
	if n == 1: # przypadek bazowy
		return 1
	return n * factorial(n - 1) # krok rekurencyjny

factorial(5) wywołuje factorial(4), które wywołuje factorial(3), aż do factorial(1), które zwraca 1. Wracając, każde wywołanie mnoży: wynikiem jest 120.

Mniejsze dane wejściowe nie muszą być mniejszą liczbą. Krótszy ciąg znaków też się sprawdzi. Ta funkcja odwraca ciąg znaków:

func reverse_text(text: String) -> String:
	if text.length() <= 1: # przypadek bazowy
		return text
	return reverse_text(text.substr(1)) + text[0]

text.substr(1) to ciąg znaków bez pierwszego znaku. Funkcja odwraca ten krótszy ciąg i dodaje pierwszy znak na końcu. Ciąg zawierający zero lub jeden znak jest już odwrócony, więc stanowi przypadek bazowy.

print(reverse_text("hello"))

olleh