Recursion: base case and recursive case · Resursif: kasus dasar dan kasus rekursif
A function that calls itself
- Recursion is when a function calls itself to solve a smaller version of the same problem.
- It needs two parts: a base case that stops, and a recursive case that shrinks the problem.
- Without a base case, it would call itself forever and crash.
Fungsi yang memanggil dirinya sendiri
- Rekursi adalah ketika sebuah fungsi memanggil dirinya sendiri untuk menyelesaikan versi masalah yang lebih kecil.
- Membutuhkan dua bagian: kasus dasar yang menghentikan, dan kasus rekursif yang mengecilkan masalah.
- Tanpa kasus dasar, ia akan memanggil dirinya sendiri selamanya dan menyebabkan crash.
The base case
- The base case is the smallest problem you can answer directly, with no more calls.
- For factorial,
0!and1!are both1— that is the base case. - Always handle the base case first, so the recursion has somewhere to stop.
Kasus dasar
- Kasus dasar adalah masalah terkecil yang bisa Anda jawab langsung, tanpa panggilan lagi.
- Untuk faktorial,
0!dan1!keduanya1— itulah kasus dasarnya. - Selalu tangani kasus dasar pertama, agar rekursi memiliki tempat berhenti.
The recursive case
- The recursive case solves the problem using the answer to a smaller one.
n! = n × (n - 1)!, sofactorial(n)returnsn * factorial(n - 1).- Each call must move closer to the base case, or it will never stop.
Kasus rekursif
- Kasus rekursif menyelesaikan masalah menggunakan jawaban dari masalah yang lebih kecil.
n! = n × (n - 1)!, sehinggafactorial(n)mengembalikann * factorial(n - 1).- Setiap panggilan harus bergerak lebih dekat ke kasus dasar, atau ia tidak akan pernah berhenti.
#include <stdio.h>
int factorial(int n) {
if (n <= 1) return 1; // base case
return n * factorial(n - 1); // recursive case
}
int main(void) {
printf("%d\n", factorial(5)); // 120
return 0;
}
Recursion over an array
- You can recurse along an array by passing an index that moves forward each call.
- The base case is "the index has reached the end" (return
0for a sum). - The recursive case is
a[i] + sum(a, i + 1, n)— this item plus the sum of the rest.
Rekursi pada array
- Anda dapat melakukan rekursi sepanjang array dengan meneruskan indeks yang maju setiap kali dipanggil.
- Kasus dasarnya adalah "indeks telah mencapai akhir" (kembalikan
0untuk penjumlahan). - Kasus rekursifnya adalah
a[i] + sum(a, i + 1, n)— item ini ditambah jumlah sisa.
Common mistakes
- Recursion needs a base case, or the call stack overflows.
- Each call must move closer to the base case.
Kesalahan umum
- Rekursi memerlukan kasus dasar, atau tumpukan panggilan akan penuh (overflow).
- Setiap pemanggilan harus bergerak lebih dekat ke kasus dasar.
Now you try
- Write the base case first, then the recursive case that calls itself on a smaller input.
- Keep test values small so the numbers stay inside an
int. - Do not write a
main— the checker provides one.
Sekarang Anda coba
- Tulis kasus dasar terlebih dahulu, kemudian kasus rekursif yang memanggil dirinya sendiri pada input yang lebih kecil.
- Jaga nilai uji tetap kecil agar angka tetap berada dalam rentang
int. - Jangan tulis
main— checker menyediakannya.
Recursion returns up · Recursion kembali ke atas
Calls split to a base case, then values return up. · Panggilan dibagi menjadi kasus dasar, kemudian nilai kembali ke atas.
Complete int factorial(int n) using recursion: return 1 for n <= 1 (the base case), otherwise n * factorial(n - 1). Do not write a main. · Lengkapi int factorial(int n) menggunakan rekursi: kembalikan 1 untuk n <= 1 (kasus dasar), jika tidak maka n * factorial(n - 1). Jangan tulis kode main.
Click Run to see the output here. · Klik Jalankan untuk melihat output di sini.
Complete int power(int base, int exp) using recursion (assume exp >= 0): base to the power 0 is 1, otherwise base * power(base, exp - 1). Do not write a main. · Lengkapi int power(int base, int exp) menggunakan rekursi (asumsikan exp >= 0): base pangkat 0 adalah 1, jika tidak maka base * power(base, exp - 1). Jangan tulis kode main.
Click Run to see the output here. · Klik Jalankan untuk melihat output di sini.
Complete int array_sum(const int a[], int i, int n) using recursion: it returns the sum of a[i] up to a[n-1]. Base case: i >= n returns 0. Do not write a main. · Lengkapi int array_sum(const int a[], int i, int n) menggunakan rekursi: fungsi ini mengembalikan jumlah dari a[i] hingga a[n-1]. Kasus dasar: i >= n mengembalikan 0. Jangan tulis kode main.
Click Run to see the output here. · Klik Jalankan untuk melihat output di sini.