Презентация на тему "Рекурсивное программирование"

Содержание

• 
  Слайд 1

  Рекурсивное программирование

  1 Рекурсия – это метод, сводящий общую задачу к некоторым задачам более узкого, простого типа Рекурсивный алгоритм – это алгоритм, который в процессе своей работы обращается сам к себе. Суть заключается в том, что при каждом вызове создается новая копия со своими переменными, но как только она заканчивает свою работу, то память, занятая этими локальными переменными, освобождается, а полученные результаты передаются в точку вызова. Рекурсивное программирование Рекурсивное программирование Recursio (лат.) - возврвщение

• 
  Слайд 2

  Рекурсия …

  2 послушать… «У попа была собака, Он ее любил. … посмотреть… встаньте между двумя зеркалами и смотрите…(не детали гардероба, нет. Отражение себя, там …) нарисовать…нарисуйте себя, где на полотне вы рисуете себя, где на полотне… Ее можно: Это примеры «бесконечной» рекурсии…

• 
  Слайд 3

  Задачи с рекурсивной формулировкой

  3 Пример: вычисление факториала натурального числа N! = 1, при N = 1 N * (N – 1)!, при N > 1 Function factorial(n: integer): longint; Begin If n = 1 then factorial:=1 else factorial:= n * factorial (n – 1); End; При использовании рекурсии необходимо обеспечить выход из подпрограммы в нужный момент, т.к. алгоритм должен быть конечным (одно из свойств).

• 
  Слайд 4
  

  4 Найдем 5! Первый вызов этой функции будет из основной программы. Например, α:= factorial(5) Function factorial Begin factorial:= 5 * factorial(4); End; Function factorial Begin factorial:= 4* factorial(3); End; Function factorial Begin factorial:= 2* factorial(1); End; Function factorial Begin factorial:= 3* factorial(2); End; Function factorial Begin factorial:= 1; End; 3 вызов (n=3) 2 вызов (n=4) 4 вызов (n=2) 5 вызов (n=1) 1 вызов (n=5) 2 *1 5 *24 4 *6 3 *2 factorial(5) = 120 α:= 120

• 
  Слайд 5

  Задание

  5 Напишите рекурсивную программу определения суммы первых n натуральных чисел: Sn = Sn-1 + n; S1 = 1. 2. Составить рекурсивную программу ввода с клавиатуры последовательность чисел(окончание ввода - 0) и вывода ее на экран в обратном порядке.

• 
  Слайд 6
  

  Пример: перевод натурального числа из десятичной системы счисления в двоичную.

  6 39 38 19 18 9 8 4 4 2 2 2 2 2 1 2 2 1 0 1 1 0 3910 = 1001112 Procedure Rec(n: integer); begin If n > 1 then Rec(n Div 2); Write(n Mod 2); End;

• 
  Слайд 7
  

  7 Procedure Rec begin Rec(n Div 2); Write(n Mod 2); End; 1 вызов (n = 39) Procedure Rec begin Rec(n Div 2); Write(n Mod 2); End; Procedure Rec begin Rec(n Div 2); Write(n Mod 2); End; Procedure Rec begin Rec(n Div 2); Write(n Mod 2); End; Procedure Rec begin Rec(n Div 2); Write(n Mod 2); End; Procedure Rec begin Write(n Mod 2); End; 2 вызов (n = 19) 3 вызов (n = 9) 4 вызов (n = 4) 6 вызов (n = 1) 5 вызов (n = 2)

• 
  Слайд 8

  Задание

  8 Написать процедуру перевода числа из десятичной системы в N- ю, при условии, что 2 ≤ N ≥ 16 и его значение вводится с клавиатуры. Каким будет условие завершения входа в рекурсию?

• 
  Слайд 9

  Напишите программу:

  9 Найти первые N чисел Фибоначчи. Каждое число равно сумме двух предыдущих чисел при условии, что первые два равны 1 (1, 1, 2, 3, 5, 8, 13, 21, …). Рекурсивная постановка данной задачи: Ф(n) = 1, если n = 1 или n = 2; Ф(n – 1) + Ф(n – 2), при n > 2

• 
  Слайд 10
  

  10 Program chisla_Fibonachi; var i,n:integer; function fib(nf:integer):longint; begin if (nf=1) or (nf=2) then fib:=1 else fib:=fib(nf-1)+fib(nf-2); end; begin readln(n); for i:=1 to n do writeln(fib(i)); end. Данная программа раскрывает недостатки рекурсии: с увеличением n глубина рекурсии многократно (во сколько?)увеличивается и выполняемая программа потребует много памяти, что может привести к переполнению стека. Если при решении есть выбор между итерацией и рекурсией, то предпочтительным выбором является итерация.

• 
  Слайд 11

  Итерация

  11 повторное выполнение некоторых действий до тех пор, пока не будет удовлетворяться некоторое условие. Большинство алгоритмов можно реализовать двумя способами: function fibon(nf:integer):longint; begin f1:=1; f2:=1; for i:=3 to n do begin f:=f1+f2; f1:=f2; f2:=f; end; fibon:=f; end; function fib(nf:integer):longint; begin if (nf=1) or (nf=2) then fib:=1 else fib:=fib(nf-1)+fib(nf-2); end; Итерацией: Рекурсией:

• 
  Слайд 12

  Выводит цифры целого положительного числа в обратном порядке

  12 Program Perevertish; Var n: longint; Procedure reverse(n: longint); begin write (n mod 10); if n div 10 0 then reverse (n div 10) end; Begin writeln(‘Введите натуральное число

• 
  Слайд 13

  Число-полиндром

  13 - число, которое имеет тот же вид при прочтении его справа налево. Например: 121, 1230321, 99 и т.п.

• 
  Слайд 14

  Решение задач

  14 Даны первый член и разность арифметической прогрессии. Написать рекурсивную функцию для нахождения: a) n-го члена прогрессии; б) суммы n первых членов арифметической прогрессии. 2. Даны первый член и знаменатель геометрической прогрессии. Написать рекурсивную функцию для нахождения: a) ее n-го члена; б) суммы n первых членов прогрессии.

• 
  Слайд 15
  

  15 3. Написать рекурсивную функцию для вычисления: а) суммы цифр натурального числа; б) количества цифр натурального числа. 4. Написать рекурсивную процедуру для вывода на экран цифр натурального числа в обратном порядке. 5. Написать рекурсивную функцию, определяющую является ли заданное натуральное число простым.

• 
  Слайд 16
  

  16 Procedure Picture1(x,y,r,r1,n:integer); Var x1,y1:integer; i:integer; Begin if n > 0 then {“заглушка”} begin circle(x,y,r);r1:=trunc(r*k2); {рисование окружности} r1:=trunc(r*k2) {вычисление радиуса орбиты} For i:=1 to 4 do begin x1:=trunc(x+r1*cos(pi/2*i); { координаты центра } y1:=trunc(y+r1*sin(pi/2*i); { i-ой окружности } Picture1(x1,y1,trunc(r*k1),r1,n-1); end; end; end;

• 
  Слайд 17
  

  17 Uses Graph; Var x,y,n,r,r1,cd,gm:integer; k1,k2:real; Procedure Picture1(x,y,r,r1,n:integer); … End; Begin Writeln(‘Введите количество уровней n’); Readln(n); x:=600 Div 2; y:=400 Div 2; Writeln(‘Введите радиус первой окружности r’); readln(r); k1:=0.3; k2:=2; Cd:=detect; gm:=1; Initgraph(cd,gm,’c:\tp7\bin’); Picture1(x,y,r,r1,n); Readln; Closegraph; End.