TechCodeview

Funkcja rekurencyjna to funkcja, której wartość w dowolnym punkcie można obliczyć na podstawie wartości funkcji w niektórych poprzednich punktach. Załóżmy na przykład, że funkcja f(k) = f(k-2) + f(k-3) jest zdefiniowana przez nieujemną liczbę całkowitą. Jeśli mamy wartość funkcji w k = 0 i k = 2, możemy również znaleźć jej wartość dla dowolnej innej nieujemnej liczby całkowitej. Innymi słowy, możemy powiedzieć, że funkcja rekurencyjna odnosi się do funkcji, która wykorzystuje swoje własne poprzednie punkty do określenia kolejnych terminów i w ten sposób tworzy sekwencję terminów. W tym artykule dowiemy się o funkcjach rekurencyjnych wraz z pewnymi przykładami.

podciąg ciąg Java

Co to jest rekurencja?

Rekurencja odnosi się do procesu, w którym proces rekurencyjny się powtarza. Rekurencyjna to rodzaj funkcji jednej lub większej liczby zmiennych, zwykle określonych przez pewien proces, który generuje wartości tej funkcji poprzez ciągłe wdrażanie określonej relacji do znanych wartości funkcji.

Tutaj zrozumiemy rekurencję na przykładzie.

Załóżmy, że zamierzasz wejść po schodach na pierwsze piętro z parteru. Aby to zrobić, musisz wykonać krok po kroku. Do drugiego stopnia można przejść tylko przez stromy pierwszy stopień. Załóżmy, że chcesz przejść do trzeciego kroku; najpierw musisz zrobić drugi krok. Tutaj wyraźnie widać proces powtarzania. Tutaj możesz zobaczyć, że z każdym kolejnym krokiem dodajesz poprzedni krok jak powtarzającą się sekwencję z tą samą różnicą między każdym krokiem. To jest rzeczywista koncepcja funkcji rekurencyjnej.

Krok 2: Krok 1 + najniższy stopień.

Krok 3: Krok 2 + Krok 1 + najniższy stopień.

Krok 4: Krok 3 + krok 2 + krok 1 + najniższy krok i tak dalej.

Zbiór liczb naturalnych jest podstawowym przykładem funkcji rekurencyjnych rozpoczynających się od jedynki aż do nieskończoności, 1,2,3,4,5,6,7,8, 9,….bezokolicznik. Dlatego zbiór liczb naturalnych wykazuje funkcję rekurencyjną, ponieważ wspólną różnicę między każdym terminem można zobaczyć jako 1; pokazuje za każdym razem, gdy następny termin powtarza się z poprzednim.

Co to jest funkcja zdefiniowana rekurencyjnie?

Funkcje zdefiniowane rekurencyjnie składają się z dwóch części. Pierwsza część dotyczy definicji najmniejszego argumentu, a druga część dotyczy definicji n-tego terminu. Najmniejszy argument jest oznaczony przez f (0) lub f (1), natomiast n-ty argument jest oznaczony przez f (n).

Postępuj zgodnie z podanym przykładem.

Załóżmy, że sekwencja to 4,6,8,10

Wyraźny wzór na powyższą sekwencję to f (n) = 2n + 2

Wyraźny wzór na powyższą sekwencję jest podany przez

fa (0) = 2

f(n) = fa (n-1) + 2

Teraz możemy otrzymać wyrazy ciągu stosując wzór rekurencyjny w następujący sposób f(2 ) f (1) + 2

f(2) = 6

fa (0) = 2

f(1) = f(0) + 2

fa (1) = 2 + 2 = 4

f(2 ) = fa (1) + 2

f(2) = 4 + 2 = 6

f(3 ) = fa (2) + 2

f(3 ) = 6 + 2 = 8

Za pomocą powyższego wzoru na funkcję rekurencyjną możemy wyznaczyć kolejny wyraz.

Co sprawia, że ​​funkcja jest rekurencyjna?

Aby jakakolwiek funkcja była rekurencyjna, potrzebny jest jej własny termin, aby obliczyć następny wyraz w sekwencji. Na przykład, jeśli chcesz obliczyć n-ty wyraz danego ciągu, musisz najpierw znać poprzedni wyraz i wyraz poprzedzający poprzedni wyraz. Dlatego musisz znać poprzedni termin, aby sprawdzić, czy sekwencja jest rekurencyjna, czy nie. Możemy zatem stwierdzić, że jeśli funkcja potrzebuje poprzedniego członu do określenia kolejnego wyrazu w sekwencji, to funkcję tę uważa się za funkcję rekurencyjną.

Wzór funkcji rekurencyjnej

Jeśli₁, A₂, A₃, A₄, A₅, A₆, ……..A_N,……jest wiele zbiorów lub sekwencji, wówczas formuła rekurencyjna będzie musiała obliczyć wszystkie warunki, które istniały wcześniej, aby obliczyć wartość

A_N= za_{n-1 +}A₁

Powyższy wzór można również zdefiniować jako wzór rekursywny na sekwencję arytmetyczną. W sekwencji wspomnianej powyżej wyraźnie widać, że jest to ciąg arytmetyczny, który składa się z pierwszego wyrazu, po którym następują pozostałe wyrazy oraz wspólnej różnicy między każdym wyrazem. Wspólna różnica odnosi się do liczby, którą do nich dodajesz lub odejmujesz.

Funkcję rekurencyjną można również zdefiniować jako ciąg geometryczny, w którym zbiory liczb lub sekwencja mają wspólny współczynnik lub wspólny stosunek. Wzór na ciąg geometryczny podano jako

A_N= za_{n-1 *}R

Zwykle funkcja rekurencyjna jest definiowana w dwóch częściach. Pierwsza to zestawienie pierwszego wyrazu wraz ze wzorem, druga to zestawienie pierwszego wyrazu wraz z regułą dotyczącą kolejnych wyrazów.

Jak napisać wzór rekurencyjny na ciąg arytmetyczny

Aby napisać wzór rekurencyjny na ciąg arytmetyczny, wykonaj podane kroki

Krok 1:

W pierwszym kroku należy sprawdzić, czy podany ciąg jest arytmetyczny czy nie (w tym celu należy dodać lub odjąć dwa kolejne wyrazy). Jeśli otrzymasz ten sam wynik, sekwencja zostanie uznana za sekwencję arytmetyczną.

Krok 2:

Teraz musisz znaleźć wspólną różnicę dla danej sekwencji.

Krok 3:

Sformułuj formułę rekurencyjną, używając pierwszego członu, a następnie utwórz formułę, używając poprzedniego członu i wspólnej różnicy; w ten sposób otrzymasz podany wynik

znak na ciąg

A_N= za_{n-1 +}D

teraz rozumiemy podany wzór na przykładzie

załóżmy, że 3,5,7,9,11 jest podaną sekwencją

W powyższym przykładzie można łatwo stwierdzić, że jest to ciąg arytmetyczny, ponieważ każdy wyraz w ciągu jest zwiększany o 2. Zatem wspólna różnica między dwoma wyrazami wynosi 2. Znamy wzór na ciąg rekurencyjny

A_N= za_{n-1 +}D

Dany,

d = 2

A₁= 3

Więc,

A₂= za_(2-1)+ 2 = a₁+2 = 3+2 = 5

A₃= za_(3-1)+ 2 = a₂+2 = 5+2 = 7

A₄= za_(4-1)+ 2 = a₃+2 = 7+2 = 9

A₅= za_(5-1)+ 2 = a + 2 = 9+2 = 11 i proces trwa.

Jak napisać wzór rekurencyjny na ciąg geometryczny?

Aby napisać formułę rekurencyjną dla formuły ciągu geometrycznego, wykonaj podane kroki:

Krok 1

W pierwszym kroku należy sprawdzić, czy podany ciąg jest geometryczny czy nie (w tym celu należy każdy wyraz pomnożyć lub podzielić przez liczbę). Jeśli otrzymasz ten sam wynik z jednego wyrazu na następny, sekwencję przyjmuje się jako sekwencję geometryczną.

Krok 2

Teraz musisz znaleźć wspólny stosunek dla danego ciągu.

Krok 3

Sformułuj formułę rekurencyjną, używając pierwszego członu, a następnie utwórz formułę, używając poprzedniego członu i wspólnego ilorazu; w ten sposób otrzymasz podany wynik

A_N= r_*A_n-1

Teraz rozumiemy podaną formułę na przykładzie

załóżmy, że 2,8,32,128 jest zadaną sekwencją

W powyższym przykładzie łatwo można stwierdzić, że jest to ciąg geometryczny, gdyż kolejny wyraz ciągu otrzymujemy mnożąc 4 przez wyraz poprzedni. Zatem wspólny stosunek dwóch wyrazów wynosi 4. Znamy wzór na ciąg rekurencyjny

A_N= r_*A_n-1

A_N= 4

A_n-1=?

Dany,

r = 4

A₁= 2

przycinanie a-b

Więc,

A₂= za_(2-1)* 4 = a₁+ * 4 = 2* 4 = 8

A₃= za_(3-1)* 4 = a₂* 4 = 8 * 4 = 32

A₄= za_(4-1)* 4 = a₃* 4 = 32* 4 = 128 i proces trwa.

Przykład funkcji rekurencyjnej

Przykład 1:

Znajdź wzór rekurencyjny dla ciągu 4,8,16,32,64, 128,….?

Rozwiązanie:

Biorąc pod uwagę sekwencję 4,8,16,32,64,128,…..

Podany ciąg jest geometryczny, ponieważ jeśli pomnożymy wyraz poprzedzający, otrzymamy wyrazy kolejne.

Aby wyznaczyć wzór rekurencyjny dla danego ciągu, należy go zapisać w formie tabelarycznej

Stąd formuła rekurencyjna w pojęciu funkcji jest dana przez

f(1) = 4, f(n) . f(n- 1)

W notacji z indeksem dolnym formuła rekurencyjna jest podawana przez

A₁= 4, a_N= 2. a_n-1