Рекурсія в паскаль, рекурсивні функції і процедури
Якщо в тілі функції зустрічається виклик самій цій функції. то це і є рекурсія.
Рекурсивний в Паскалі можуть володіти як функції, так і процедури.
По суті, рекурсія може бути нескінченною. Але, як і будь-який інший алгоритм, вона зобов'язана видавати результат своєї роботи за якесь певне кількість операцій.
Тому важливо: На кожному кроці виконання рекурсивного тіла процедури або функції обов'язково або зміна параметра даної функції, або наявність умови при якому вона більше себе не викликатиме!
Розглянемо простий приклад використання рекурсивної процедури:
Приклад: Надрукувати послідовність чисел в зворотному порядку, використовуючи рекурсивний виклик процедури. напpимеp:
row (5) = 5 4 3 2 1
З умови задачі ясно, що умовою завершення рекурсії буде сам аргумент функції, який слід зменшувати на одиницю, поки він> = 1.
procedure row (n: integer); begin if n> = 1 then begin write (n, ''); row (n-1) end; end; begin row (10); end.
Тепер розглянемо більш складний приклад використання рекурсії в Паскаль.
Приклад: Написати рекурсивну процедуру, що виводить цифри, переданого їй у якості фактичного параметра числа, в зворотному порядку.
Наприклад: при переданому функції числі 3078. має в підсумку повернути 8703
Використовувати операції div і mod
procedure reverse (n: integer); begin write (n mod 10); if (n div 10) <> 0 then reverse (n div 10) end; begin writeln; reverse (3078); end.
Рекурсія: Роздрукувати послідовність, використовуючи рекурсію:
25,23,21,19,17 ... 0
А тепер подивимося, як використовується рекурсія при обчисленні факторіала в Паскаль.
Приклад: Створити рекурсивную функцію для обчислення факторіала числа
Підказка:
2! = 2 * 1 = 2
3! = 3 * 2 * 1 = 6
Виводимо формулу a! = A * ((a-1)!)
var x: integer; function fact (a: integer): integer; begin if (a<=1) then a:=1 else a:=a*(fact(a-1)); fact:=a; end; begin writeln('Число?'); readln(x); writeln(fact(x)); end.
Рекурсія: Написати рекурсивну функцію sumTo (n). яка для даного n обчислює суму чисел від 1 до n. наприклад:
sumTo (1) = 1
sumTo (2) = 2 + 1 = 3
sumTo (3) = 3 + 2 + 1 = 6
.
Рекурсія. Написати рекурсивну функцію визначення ступеня числа.
var x, y: integer; function stepen (a, b: integer): integer; var. begin. end; begin writeln ( 'число?'); readln (x); writeln ( 'ступінь?'); readln (y); writeln (stepen (x, y)); end.
Рекурсія: Необхідно зімітувати роботу циклу for. Виводити кожен раз слово «привіт» і значення лічильника. Для цього використовувати змінну лічильника кроків, яку потрібно реалізувати, як параметр процедури. Другий параметр - загальна кількість кроків (кількість ітерацій циклу).
Рекурсія: Знайти НСД методом Евкліда. Використовувати рекурсивную процедуру.
Для чисел 3430 і 1365:
залишок від ділення 3430 на 1365
3430 mod 1365 = 700
залишок не дорівнює нулю, повторимо ту саму дію, підставивши замість першого числа друге, а замість другого - залишок
1365 mod 700 = 665
залишок теж нуль, тому ще одну поділку
700 mod 665 = 35
залишок теж нуль, тому ще одну поділку
Рекурсія: Роздрукувати перші 10 чисел Фібоначчі (до 21), використовуючи рекурсивну процедуру з двома параметрами.
Результат повинен бути: 1 2 3 5 8 13 21 34 55 89
Доповніть код: