Книга программиста/Задачи на рекурсию

К оглавлению | Назад | Вперёд

Все программы, код которых выложен здесь, являются работоспособными. На момент написания программ использовалась среда PascalABC.Net 3.0 (и 3.3).

PascalABC.Net

Произведение

Найти произведение первых n членов такой последовательности, что каждый следующий ее член больше предыдущего на 2.

function F(n: integer): integer;
  function F2(x, k, n: integer): integer;
  begin
    if k = n then Result := x else Result := x * F2(x + 2, k + 1, n);
  end;

begin
  Result := F2(1, 1, n);
end;

begin
  for var i := 1 to 10 do
    Writeln(F(i));
end.

Дроби

Вычислить выражение вида: x^n / n!.

function F(x: real; n: integer): real;
begin
  if n = 0 then Result := 1 else Result := x / n * F(x, n - 1);
end;

begin
  Writeln(F(ReadlnReal('X:'), ReadlnInteger('N:')));
end.

Остаток от деления a на b

function F(a, b: integer): integer;
begin
  if a < b then Result := a else Result := F(a - b, b);
end;

begin
  Writeln(F(ReadlnInteger('A:'), ReadlnInteger('B:')));
end.

Определение степени пятерки

Описать рекурсивную функцию, которая вычисляет, какой степенью числа 5 является натуральное число a. Если a не степень пяти, функция должна вернуть число -1.

function F(a: integer): integer;
begin
  if a = 1 then
    Result := 0
  else if a mod 5 <> 0 then
    Result := -1
  else
  begin
    Result := F(a div 5);
    Inc(Result, Ord(Result <> -1));
  end;
end;

begin
  Writeln(F(ReadlnInteger('A:')));
end.

Возведение числа в степень

function F(a, n: integer): real;
begin
  if n = 0 then Result := 1
  else if n > 0 then Result := a * F(a, n - 1) else Result := 1 / F(a, Abs(n));
end;

begin
  Writeln(F(ReadlnInteger('A:'), ReadlnInteger('B:')));
end.

Используется формула: x^(-n) = 1 / x^n.

Максимальная цифра числа

function MaxDigit(a: integer): integer;
begin
  if a < 10 then MaxDigit := a
  else
  begin
    var l := a mod 10;
    var m := MaxDigit(a div 10);
    if m > l then Result := m else Result := l;
  end;
end;

begin
  Writeln(MaxDigit(413));
end.

Добавление цифр

Добавление в конец

function AddAfter(x: integer; a: byte) := x * 10 + a;

begin
  Writeln(AddAfter(123, 4));
end.

Добавление в начало

function AddBefor(x: integer; a: byte): integer;
begin
  if x < 10 then
    Result := a * 10 + x
  else
    Result := x mod 10 + AddBefor(x div 10, a) * 10;
end;

begin
  Writeln(AddBefor(123456, 9));
end.

Вывод числа наоборот

procedure Print(x: integer);
begin
  Write(x mod 10);
  var d := x div 10;
  if d <> 0 then Print(d);
end;

begin
  Print(123);
  Writeln();
end.

Равенство сумм цифр числа и суммы, передаваемой в s

function IsEqual(x: integer; s: integer): boolean;
begin
  if s < 0 then
    Result := false
  else
    if x < 10 then 
      Result := x = s
    else
      Result := IsEqual(x div 10, s - x mod 10);
end;

begin
  Writeln(IsEqual(123, 5));
end.

Количество делителей числа

function Dividers(N: integer): integer;{N>1}
  function DivF(k: integer): integer;
  begin
    if k > N div 2 then
      Result := 0
    else
      Result := Ord(N mod k = 0) + DivF(k + 1)
  end;

begin
  Result := DivF(2)
end;

begin
  Writeln(Dividers(12));
end.

Числа Фибоначчи

function F(n: integer): integer;
begin
  if n <= 2 then Result := 1 else Result := F(n - 1) + F(n - 2);
end;

begin
  for var i := 1 to 10 do
    Writeln(F(i));
end.

Возведение экспоненты в степень с заданной точностью

var
  Eps, X: real;

function F(): real;
  function F2(d: real; n: integer): real;
  begin
    Result := d;
    if Result > Eps then
    begin
      Inc(n);
      d := d * X / n;
      Result := Result + F2(d, n);
    end
  end;

begin
  Result := F2(1, 0);
end;

begin
  Readln(Eps, X);
  Writeln(F());
end.

Вычисление суммы с заданной точностью

Найти сумму всех членов последовательности таких, что каждый из них по модулю больше Eps. Остановиться на том члене, который по модулю меньше Eps. Каждый член последовательности равен: (-1)^i / i!.

var
  Eps: real;

function F(): real;
  function F2(factr, i: integer): real;
  begin
    var j := i + 1;
    var n := (1 - 2 * (i mod 2)) / factr;
    if Abs(n) < Eps then Result := n else Result := n + F2(factr * j, j);
  end;

begin
  Result := F2(1, 1);
end;

begin
  Readln(Eps);
  Writeln(F());
end.

Максимальный элемент массива

const
  N = 10;

type
  TArray = array [0..N - 1] of integer;

var
  A: TArray;

function MaxF(a: TArray; i: integer): integer;
begin
  Result := i > 0 ? Max(a[i], MaxF(a, i - 1)) : a[0];
end;

begin
  for var i := 0 to N - 1 do
    A[i] := Random(10);
  Writeln(A);
  
  Writeln(MaxF(A, N - 1));
end.

Python 3

Произведение

def F(n):
  def F2(x, k, n):
    if k == n:
      return x
    else:
      return x*F2(x + 2, k + 1, n)
    
    return F2(1, 1, n)

for i in range(9):
    print('{0}\n'.format(F(i + 1)))

Дроби

def F(x, n):
  if n == 0:
    return 1
  else:
    return x/n*F(x, n - 1)

print(F(int(input('X:')), int(input('N:'))))

Остаток от деления а на b

def F(a, b):
  if a < b:
    return a
  else:
    return F(a - b, b)

print(F(int(input('A:')), int(input('B:'))))

Определение степени пятерки

def F(a):
  if a == 1:
    return 0
  elif a%5 != 0:
    return -1
  else:
    result = F(a//5)
    result += result != -1
    return result

print(F(int(input('A:'))))

Возведение числа в степень

import math

def F(a, n):
  if n == 0:
    return 1
  elif n > 0:
    return a*F(a, n - 1)
  else:
    return 1/F(a, math.fabs(n))

print(F(int(input('A:')), int(input('B:'))))