Penjelasan Algoritma Rekursif | Algoritma Faktorial dan Pangkat | Algoritma Pertemuan 57
Summary
TLDRThis educational video script delves into the concept of recursion in algorithms, which the author considers both challenging and beautiful. It explains recursion as a problem-solving technique where the solution involves the problem itself, often implemented within functions that call themselves. Using the analogy of mirrors reflecting each other to illustrate the self-referencing nature of recursion, the script provides a detailed example with factorial calculations. It breaks down the recursive process into base cases and recursive cases, demonstrating how functions call themselves with modified parameters until a base condition is met. The script also touches on the concept of exponentiation as another example of recursion, guiding viewers through the mathematical and algorithmic understanding of these computational techniques.
Takeaways
- 😀 The script introduces the concept of recursive algorithms, which the speaker considers one of the most challenging and beautiful parts of the study of algorithms.
- 🧠 Recursive algorithms are defined as techniques that solve problems by containing the problem's definition within the solution itself, often implemented within a function that calls itself.
- 🪄 The script uses the analogy of mirrors facing each other to illustrate the concept of recursion, where an image within a mirror reflects another image, and so on, infinitely.
- 🔢 The script explains recursion with a mathematical example, the factorial function, which is calculated by multiplying a series of descending natural numbers down to 1.
- 📚 The basis and recursion parts of a recursive function are defined: the basis provides a stopping condition, while the recursion part defines the function in terms of itself.
- 💡 The script provides a step-by-step breakdown of how recursion works in the context of calculating factorials, emphasizing the self-referential nature of the process.
- 📉 The script contrasts recursive solutions with iterative ones, highlighting that recursion does not require loops or explicit iteration constructs like 'for' or 'while'.
- 📝 An algorithmic representation of a recursive function is provided, showing how the function is defined to handle base cases and recursive cases.
- 🔄 The script describes the process of a recursive function call and how it 'unwinds' or backtracks through the function calls until it reaches the base case.
- 💻 The speaker encourages viewers to implement recursive algorithms in programming languages and to explore more examples to gain a deeper understanding of recursion in algorithmic problem-solving.
Q & A
What is the main topic discussed in the script?
-The main topic discussed in the script is the concept of recursion in algorithms, particularly in the context of computer programming.
How is recursion defined in the script?
-Recursion is defined as a technique for solving a problem where the solution itself contains the problem's definition, often implemented within a function that calls itself.
What is the significance of recursion in algorithms?
-Recursion is significant in algorithms as it allows for the elegant and efficient solution of problems that can be broken down into smaller, similar subproblems, such as calculating factorials or handling nested data structures.
Can you provide an example of recursion from the script?
-An example of recursion from the script is the calculation of factorials, where the factorial of a number n is defined as n times the factorial of n-1, with the base case being that the factorial of 0 is 1.
What is the 'basis' in the context of recursive algorithms?
-The 'basis' in recursive algorithms refers to the base case or the simplest instance of the problem that can be solved directly without further recursion, such as when n is 0 in the factorial example.
What is the 'recurrence' in the context of recursive algorithms?
-The 'recurrence' in recursive algorithms refers to the part of the algorithm where the function calls itself with a modified argument, such as reducing the problem size in each recursive call until it reaches the base case.
How does the script illustrate the concept of recursion with mirrors?
-The script uses the analogy of standing between two facing mirrors to illustrate recursion. As you look into one mirror, it reflects the other mirror, which in turn reflects you, creating an infinite sequence of reflections, similar to how a recursive function calls itself.
What is the practical application of recursion mentioned in the script?
-The script mentions the practical application of recursion in calculating mathematical functions like factorials and powers, where the solution involves breaking down the problem into smaller instances of the same problem.
How does the script explain the process of a recursive function calling itself?
-The script explains that a recursive function calls itself with a modified argument until it reaches the base case, at which point it starts returning values back up the call stack, ultimately solving the original problem.
What is the importance of the base case in recursion?
-The base case is crucial in recursion as it defines the stopping condition for the recursive calls. Without a proper base case, the recursion could continue indefinitely, leading to a stack overflow or infinite loop.
Outlines
🧠 Introduction to Recursive Algorithms
The speaker begins by introducing the concept of recursive algorithms, which they consider one of the most challenging yet beautiful topics in the study of algorithms. They explain that recursion involves a function calling itself to solve a problem, and this can be visualized through the metaphor of standing between two mirrors facing each other, creating an infinite reflection. The speaker uses the example of factorial calculation to illustrate recursion, explaining how the factorial of a number is calculated by multiplying it by the factorial of the number minus one, down to the base case where the factorial of zero is defined as one. This sets up the foundation for understanding how recursive algorithms work and their practical applications.
🔍 Deep Dive into Recursive Factorials
This paragraph delves deeper into the recursive calculation of factorials, highlighting how each factorial calculation is dependent on the result of a smaller instance of the same problem. The speaker mathematically defines the factorial function, explaining that factorial 'n' is 'n' times factorial 'n-1', with the base case being factorial '0' which equals one. They emphasize the importance of understanding both the base case and the recursive case in a recursive function. The speaker also discusses how recursive functions are implemented in programming, using the factorial function as an example to demonstrate how the function calls itself with decremented arguments until it reaches the base case.
📚 Recursive Power Calculations
The speaker transitions into explaining how recursion can be applied to calculate powers. They clarify that any number raised to the power of zero equals one, and for any positive integer 'n', the power calculation involves multiplying the base number by the result of the base number raised to the power of 'n-1'. The base case for this recursive process is when 'n' equals zero. The speaker outlines the algorithm for calculating powers recursively, emphasizing that no loops or iterations are used in this process, unlike iterative methods. They provide a step-by-step explanation of how the recursive power function works, using the example of calculating 5 to the power of 3.
🚀 Practical Implementation of Recursion
In the final paragraph, the speaker discusses the practical implementation of recursive algorithms in programming languages. They provide a detailed walkthrough of how recursive functions for factorial and power calculations are translated into code. The speaker emphasizes the importance of understanding the recursive process, from the initial function call down to reaching the base case and then unwinding the stack to return the final result. They conclude by encouraging viewers to explore more examples and cases of recursive algorithms in programming, hinting at the depth and广泛应用 of this concept. The speaker also reminds viewers to subscribe for more content and ends the session with a farewell and blessings.
Mindmap
Keywords
💡Algorithm
💡Recursive
💡Factorial
💡Base Case
💡Recursive Case
💡Procedure
💡Mirror Image
💡Function
💡Exponential
💡Implementation
Highlights
Introduction to the concept of recursive algorithms, which are considered both challenging and beautiful within the study of algorithms.
Definition of recursion as a technique for solving problems by including the problem's definition within the solution.
Explanation that recursion is implemented within a function that calls itself.
Discussion on the everyday example of recursion through the reflection of mirrors facing each other.
The mathematical representation of recursion in the context of factorial calculation.
Illustration of how factorial calculation inherently contains recursive properties.
Description of the base case in recursion, which defines when the recursive process should stop.
Explanation of the recursive case, where the function calls itself with a modified argument.
Coding example of a recursive function to calculate factorials.
Simulation of how the recursive factorial function works step by step.
Introduction to the concept of exponentiation and its recursive nature.
Explanation of the base case for exponentiation, where any number to the power of zero equals one.
Recursive formula for calculating powers, demonstrating the self-referential nature of the process.
Coding example of a recursive function to calculate powers.
Simulation of the recursive power function, showing the step-by-step calculation process.
Conclusion and summary of the basic understanding of recursion in algorithmic problem-solving.
Encouragement for viewers to explore more examples and implementations of recursive algorithms.
Transcripts
e-cash Assalamualaikum warahmatullahi
wabarakatuh teman-teman semua kita akan
belajar satu buah materi yang saya pikir
dalam mata pelajarannya atau dalam ilmu
pelajaran algoritma ini adalah eh bagian
yang menurut saya paling sulit itu ya
Selama saya belajar algoritma namun ini
adalah bagian paling indah dalam tanda
kutip dari ei5 algoritma itu sendiri
yaitu adalah rekursif ya algoritma
rekursif ini eh 1 bab terakhir kalau
kita mau belajar tentang agoritma
menarik kursi itu apa Jadi secara
definisi tekstual ya ini mohon maaf agak
membumi membingungkan mungkinnya dari
definisinya rekursif adalah teknik
menyelesaikan persoalan dimana didalam
nah di dalam menyelesaikan persoalan itu
mengandung definisi persoalan itu
sendiri ya eh atau dalam bentuk
implementasinya nanti rekursif ini
diimplementasikan dalam sebuah fungsi
tentu Sebelumnya kan kita sudah belajar
apa itu fungsi Apa itu prosedur yang
tidak langsung si tersebut nanti
memanggil fungsi itu sendiri gitu itu
rekursif secara implementasi sebenarnya
eh tidak hanya dalam sebuah fungsi sih
dalam prosedur pun juga tentu nanti
implementasinya bisa hanya lazimnya
ekskursif ini diimplementasikan dalam
sebuah fungsi na dalam contoh keseharian
misalkan kita berdiri di satu lorong
Gimana Di Dinding antar dua lorong itu
ada cermin yang saling berhadapan Ketika
kita melihat cermin itu maka cermin ini
akan memantulkan cermin di dalam kita Ed
sang Kita dimana di belakang di cermin
di belakang kita itu ada kita dengan
cermin yang di depan kita lagi kalau
kemudian di cermin yang di depan kita
ada kita lagi terus ini dan seterusnya
ada di dalam satu buah cermin ada kita
yang ada cerminnya lagi lalu kemudian
dicerminkan ada kita lagi dengan cermin
lagi dan seterusnya teman-teman kalau
datang anak cowok misalkan nya pergi ke
apa namanya babersop GTA twang cukur di
depan wajah kita ada cermin di belakang
kita ada cermin Maka kalau kita melihat
cermin yang ada di belakang kita itu ada
cermin kita lagi GTA tentu kalau
cerminnya benar-benar berhadapan atau
non bisa coba-coba hadapan dua buah
cermin atau kalau kita misalkan ada di
lift yang dimana live itu Sisinya adalah
cermin pasti kita akan melihat Sisi
cermin itu ada kita dan cermin lagi
terus dan seterusnya Nah itu gambaran
bagaimana rekursif di dalam dunia
jadi dalam satu buah bingkai persoalan
di dalamnya ada persoalan itu sendiri
dan di dalamnya ada persoalan itu
sendiri begitu ya Nah nanti kita coba
lihat dalam konteks algoritma contoh
misalkan kita punya persoalan perulangan
faktorial ya faktorial se0 itu satu
faktorial satu itu satu faktorial 2 itu
satu kali dua faktorial tiga itu satu
kali dua kali tiga faktorial 4 itu satu
kali dua kali tiga kali empat dan faktor
ya lima itu satu kali dua kali tiga kali
empat kali lima nah ini contoh tentang
faktorial ini sudah sering dibahas di
video-video sebelumnya teman-teman
silahkan cek video-video saya yang
algoritma soal faktorial baik itu di
Sumba perulangan ataupun F ungsi Kalau
nggak salah ada ya Bisa cek lagi di sana
Nah ternyata Wow proses melakukan
faktorial ini ini juga sebenarnya
memiliki
sifat rekursif Kenapa karena kalau kita
lihat Oke faktorial nol itu memang satu
Ternyata faktorial satu itu adalah
faktor yang nol dikali satu dan
faktorial 2 itu adalah faktorial satu
dikali faktorial 2 faktorial tiga itu
adalah faktorial 2 dikali dengan tiga
faktorial 4 itu adalah faktorial tiga
dikali dengan 4G dan faktorial 5 itu
adalah faktorial 4 dikali lima silakan
teman-teman di paus video ini lalu Coba
lihat antara kiri dan kanan lihat ya Ini
satu adalah faktorial satu kali dua
inhaled nih mulai tiga kelihatan Ya
gimana tiga itu adalah faktorial 2
sebenarnya satu kali dua itulah
faktorial 2 jadi yang kanan ini adalah
pola rekursif yang kiri perulangan ada
biasanya Eh rekursif ini nanti kita
menyelesaikan persoalan-persoalan yang
bentuknya juga perlu
dan ya cukup silakan di-pause dipandangi
antara kiri dengan kanan oke kalau sudah
di Paus sudah bisa dipahami dari contoh
ini kita lanjut nah di dalam persoalan
faktorial terdapat persoalan faktorial
itu sendiri lihat di dalam faktor yang
empat itu terdapat persoalan faktorial
3gnya jadi dalam faktorial ada persoalan
faktorial itu sendiri nah kalau kita
Tuliskan dalam bentuk eh matematika
faktorial dari n itu kan satu kali dua
kali seterusnya sampai dengan n min1
dikalikan dengan n ya jadi faktorial
dari n itu adalah a n kurang satu
faktorial dikalikan dengan seperti ini
ya faktorial 4 itu adalah empat kurang
satu faktorial yaitu tiga faktorial
dikalikan dengan empat dia Jadi ini
korelasinya dengan rumus yang ada di
bawah sini ya
begitu ya nah jadi kita lihat di sini n
faktorial itu dia akan bernilai 1 jika
n-nya itu adalah nol lalu kemudian dia
akan bernilai n caliente in 1 faktorial
yang ini dengan posisinya ditukar aja
jadi nw-1 faktorialnya pindah ke kanan
kalau NY itu lebih besar dari nol ya
jadi dia akan bernilai 1 kalau NY itu
nol sedangkan dia akan bernilai n * n
faktorial kalau dia lebih besar dari nol
itu kita pindahkan ke sini rumus yang
barusan nah yang bagian atas ini ini
disebut dengan basis-basis ini adalah
bagian yang mendefinisikan secara
eksplisit sebuah Nilai N kalo Omnya nol
maka nilainya satu eksplisit kan dan
basis in
ini akan menyatakan berhentinya satu
buah proses rekursif dan dalam rekursi
itu fungsi memanggil fungsi-fungsi
memanggil fungsi lagi ia memanggil
dirinya sendiri nah kapan berhentinya
Nah itu dinyatakan dengan basis ini
basis ini menyatakan eh bagian
berhentinya satu buah rekursif sedangkan
yang bagian bawah ini disebut rekaren ya
yang mendefinisikan dirinya itu sendiri
lihat Let's ini n faktorial adalah Endi
kali N1 faktorial jadi dalam faktorial
itu ada faktorial itu sendiri bagaimana
algoritmanya kita definisikan dalam
sebuah fungsi kita tulis function
faktorial an integer jadi dia menerima
satu buah input nilai Jejer lalu
mengembalikan lagi intezaar nah kita
langsung ke bagian algoritmanya karena
kita tidak perlu mendefinisikan dulu
sesuatu Nah lihat di sini ih Anne
Avantie sama dengan nol Den riten satu
ya basis ini menyatakan berhenti
Hai Jadi kalau Omnya nol yang paling
atas ini kliennya nol Maka dia
mengembalikan nilai satu ngaji kah Tidak
maksudnya lebih besar dari nol maka
repaint disini LED ya n dikalikan dengan
N1 faktorial jadi dik dari sini jadinya
kayak gini Endi kali dengan faktorial
jadi memanggil fungsi faktorial lagi
cuman inputnya adalah enmind satu ya
jadi nn yang ini ms1 nah ini eh
penulisan algoritma seperti ini jadi
untuk menghitung faktorial kita lihat di
sini enggak ada perulangan enggak ada
Luffy gak ada voernya kau teman belajar
video-video eh video sebelumnya tentang
faktor yg akan ada perulangan kali ini
ada perulangannya ia akan mengambil
fungsi faktorial Um memanggil fungsi
faktorial itu sendiri tapi dengan
inputnya adalah
[Musik]
Hai nah Gambaran simulasinya seperti apa
kau ini etnis dulu ya enif untuk menutup
yang ini Oke jadi misalkan kita Panggil
fungsi faktorial 3 ia akan masukkan ke
lagi bagian algoritmanya jika cek dulu
apakah 3 = 0 tentu Enggak kan maka masuk
ke yang esnya ya tadi yang F saya elne
itu adalah n kali faktorial min 1 jadi
masuk ke f*** edisi fungsi faktorial ini
akan memanggil faktorial yang lain elne
akan tiga kali faktorial 22 ini dari
mana tiga kurang satu memanggil ke
fungsi faktorial 2 edit di bagian
faktorial 2 ini di cek lagi apakah 2 = 0
tentu tidak maka dia akan memanggil lagi
fungsi faktorial dimana disini n-nya
sekarang 2 dikali dengan faktorial 2 min
1 Jadi dua di California le1 berarti
memanggil fungsi faktorial 2 Ed
hai eh sorry memanggil fungsi faktorial
satu lalu cek lagi apakah 1 = 0 enggak
maka dia manggil lagi faktorial diisi
dengan satu karenanya satu dikali
faktorial nol Ya karena ini satu kurang
satu Kance tiap masuk fungsi faktorial
itu didalamnya itu dikurangi dengan eh16
maka disini memanggil faktor yang nol
Apakah 0 = 0 betul maka dia merica meren
ya return value faktorial satu maka
fungsi yang ini dia merit nilai satu kau
ini meneliti nilai satu maka dia akan
merugikan ke fungsi Yang sebelumnya Yang
ini abstrak disini ini adalah satu ya
dikalikan dengan satu yang ini maka
nilainya adalah 1 dan ini kan satu
digali dengan faktorial 0eh di kalian 40
40 itu satu ia mengambil kalian nilai
satu yang nilai satu ini akan Mas
fungsi sistem yang di atasnya yang ini
kita lihat di sini dua dikali faktorial
satu faktor yang satu tadi nilainya
sudah satu pakai maka 2 dikali 1 = 22
akan mengembalikan ke nilai faktorial
yang diatasnya yang ini adalah tiga
dikali dengan faktorial 2 faktorial 2
itu dua berarti tiga dikalikan dengan
dua jenis = 6 jadi kalau kita masukin
faktorial 3 Maka hasilnya adalah nilai 6
= kalau kita menggunakan faktor yang
akan satu kali dua kali tiga itu enam
satu kali dua kedua dua kali 36 nah ini
acara berpikir bagaimana menghitung
faktorial menggunakan rekursif oke itu
satu contoh naskah kita contoh masuk ke
kasus yang berikutnya ya ini setiap
kasus saya langsung buat dan dalam share
video biasanya saya pisah enggak papa
videonya lebih panjang
sedikit layak nyapres Sekarang kita akan
masuk tentang pangkat Nah kita tahu
bahwa apangkat n itu sama dengan adik
Aliya kali dan seterusnya sebanyak n
jadi kita bisa tahu bahwa Apa ngaten itu
sebenarnya Aa dikalikan dengan apangkat
enmind satu jadi Abang Kapten itu ia
akan menghasilkan nilai satu jika enak
0erusahaan misalkan 55 pangkat n ya ya
pasti satu iya pasti satu kalau enyak
nol karena berapapun dipangkatkan nol
itu pasti nilainya satu tapi ia akan
mendapatkan nilai yang lain kalau Angle
lebih dari nol adalah akal ia pangkat
min 1 ya Jadi yang ini adalah basisnya
yang ini adalah rekannya itu ya
eh sebentar contoh misalkan eh kita
lihat ya bahwa dua pangkat nol itu kan
satu ya karena berapapun dipangkatkan
nol itu satu nah kalau dua pangkat-1 itu
kan sebenarnya dua dikali dua pangkat
nol ya dua pangkat satu Tekan dua
berarti dua dikali dengan satu lalu
kemudian dua pangkat dua itupun
sebenarnya dua dikali dua ^ 12 pangkat
dua itu empat dan bukannya 2 ^ 1 itu
adalah dua lalu kemudian dua pangkat
tiga itu adalah dua dikali dua pangkat
dua dan dua pangkat 4 itu adalah dua
dikali dua pangkat tiga jadi seperti ini
ya jikalau dua pangkat lima itu berarti
dua dikali dua pangkat 4 yang dimaksud
orang satu nah ini dalam proses
menghitung pangkat kita bisa melihat
bahwa di sini ada proses rekursif jadi
ada persoalan yang didalamnya ada
persoalan itu sendiri
Hai yang bagaimana kemudian eh
implementasinya atau kita menuliskannya
dalam notasi algoritma kita buat disini
pungsi ^ ia menerima masukan a&n ini eh
iphonenya integer dan merekam value
typenya integer tadi sini Aini sebagai
nilai n ini sebagai Sorry nilai angkanya
ini sebagai pangkatnya jadi kalau kita
menulis menghitung 5 ^ 2 berarti 5,2
atau misalnya kita mencari dua pangkat 4
berarti 2,4 jadi bagian algoritmanya
kita langsung saja lihat disini event =
0 y n ini adalah pangkatnya seperti tadi
maka dia rhythm satu sebagai basisnya
jika tidak jika n-nya tidak sama dengan
nol lebih besar dari nol maka riten ak5
ya ahli ^ a koma min 1 ya jadi baritana
dikalikan dengan
Mbak koma n pangkat min 1 enya berkurang
tadi misalkan eh apa namanya kedua
pangkat 3 masuk ke sini berarti dua
pangkat dua anaknya berkurang lalu
disini dengan enif ditutup udah selesai
lihat di sini dalam proses pemangkatan
itu kita tidak melakukan perulangan
enggak ada luping di sini enggak ada for
disini Bagaimana simulasinya gambaran
simulasinya misalkan kita mau
memangkatkan 5pangkat 35 pangkat tiga
itu lima kali lima kali 55 kali 525 25
kali lima itu 125 nah ketika kita
memanggil fungsi pangkat 5,5 kita cek
inikan entengnya itu yang di belakang
ini apakah 3 = 0 tentu tidak maka disini
^ ini ^ ya maksudnya ^ diisikan rhythm
ya pangkat yang ini diisi dengan 5
^ 5,2 karena disini min1 tadi kanannya
awalnya tiga sekarang min1 Oke berarti
manggil fungsi pangkat 5,2 ^ 5,2 cek
lagi apakah 2 = 0 tidak maka masuk lagi
ke lksnya lima kali ^ 5,1 karena 2-nya
dikurangi satu maka cek lagi di sini
Apakah n y = 0 1 tidak sama dengan nol
tentu maka keels lagi ^ diisi dengan
lima kali ^ 5,0 ya di sini NY sudah nol
Apakah 0 = 0 betul maka disini ^
mengembalikan return value nilainya satu
maka ini mengambil mengembalikan nilai
satu fungsi yang paling bawah ini
mengembalikan nilai satu nilai satu ini
akan masuk ke sini begitu masuk ke sini
berarti lima kali Satukan 5pangkat 5,0
itu kan satu berarti lima kali lima kali
satu itu sama dengan 55 ini akan masuk
lagi ke yang ini 5 dikali pangkat 5,15
itukan 5 berarti lima kali lima itu
adalah 25 lalu 25 itu akan masuk lagi ke
sini balik kesini 5 eh ^ 5,2 itu adalah
25 jadi lima kali 25 adalah 125 itu
gambaran Bagaimana hasil atau proses
running kalau sih algoritma angkat tadi
dijalankan kalau kita masukin ^ 5,3 Maka
hasilnya akan seperti ini ya prosesnya
dia akan memanggil fungsi manggil fungsi
manggil fungsi manggil fungsi sampai
dibungkus yang terakhir ketemu basisnya
di sini levisnya kan yang ini maka dia
akan trackback kebelakang lalu kemudian
mereka value 125 tentu nanti akan
menarik kalau kita coba proses ini dalam
bahasa pemograman Ok teman-teman sampai
di sini penjelasan tentang rekursif tadi
teman-teman akan
the melihat contohnya dalam bahasa
pemograman kita coba nanti
implementasikan dipiten dan banyak
sebenarnya kasus-kasus dalam konsep
algoritma pemograman itu yang
penyelesaian yaitu dengan rekursif Ya
itu aja eh basic penjelasan rekursif
tentu tidak akan cukup untuk membahas
seluruh contohnya Semoga teman-teman
bisa paham tentang bagian yang ini
sampai ketemu lagi di video-video
selanjutnya saridon Ilyas Jangan lupa
untuk subscribe ya kalau belum subscribe
Terima kasih salam alaikum
warahmatullahi wabarakatuh
5.0 / 5 (0 votes)