Fibonacci और Factorial

Factorial एक number को हर छोटे number से multiply करना है, जैसे friends को line up करने के कितने तरीके हैं count करना, जबकि Fibonacci हर number पिछले दो के sum से बनाता है, एक बढ़ते rabbit family जैसा।

In this page:

Factorial
Fibonacci
Recursive Comparison
Memoization Idea
Practice

Syntax

markup

def factorial(n):
    if n <= 1:
        return 1
    return n * factorial(n - 1)

def fibonacci(n):
    if n <= 1:
        return n
    return fibonacci(n - 1) + fibonacci(n - 2)

Factorial

n का factorial (n! लिखा गया) n तक हर positive integer का product है, और यह आमतौर पर recursion सिखाने के लिए उपयोग होने वाला पहला example है क्योंकि इसकी recursive definition (n! = n गुणा (n-1)!) code से लगभग बिल्कुल मेल खाती है।

उदाहरण: Factorial

#include <iostream>
using namespace std;
int factorial(int n) {
	if (n <= 1) return 1;
	return n * factorial(n - 1);
}
int main() {
	cout << factorial(5);
	return 0;
}

public class Main {
	static int factorial(int n) {
		if (n <= 1) return 1;
		return n * factorial(n - 1);
	}
	public static void main(String[] args) {
		System.out.println(factorial(5));
	}
}

def factorial(n):
    if n <= 1:
        return 1
    return n * factorial(n - 1)

print(factorial(5))

#include <stdio.h>
int factorial(int n) {
	if (n <= 1) return 1;
	return n * factorial(n - 1);
}
int main() {
	printf("%d", factorial(5));
	return 0;
}

Fibonacci

Fibonacci sequence हर number को इससे पहले वाले दो के sum के रूप में define करता है (0, 1, 1, 2, 3, 5, 8...), इसे एक natural दूसरा recursion example बनाते हुए क्योंकि, factorial के विपरीत, इसे प्रति step एक के बजाय दो recursive calls चाहिए।

उदाहरण: Fibonacci

#include <iostream>
using namespace std;
int fib(int n) {
	if (n <= 1) return n;
	return fib(n - 1) + fib(n - 2);
}
int main() {
	cout << fib(7);
	return 0;
}

public class Main {
	static int fib(int n) {
		if (n <= 1) return n;
		return fib(n - 1) + fib(n - 2);
	}
	public static void main(String[] args) {
		System.out.println(fib(7));
	}
}

def fib(n):
    if n <= 1:
        return n
    return fib(n - 1) + fib(n - 2)

print(fib(7))

#include <stdio.h>
int fib(int n) {
	if (n <= 1) return n;
	return fib(n - 1) + fib(n - 2);
}
int main() {
	printf("%d", fib(7));
	return 0;
}

Recursive Comparison

Factorial recursion linear है — हर call बिल्कुल एक और call करती है, इसलिए total work n के अनुपात में बढ़ता है। Fibonacci का naive recursion हर step पर दो calls में branch होता है, इसलिए इसका total work exponentially बढ़ता है भले ही final numbers simple हों।

उदाहरण: Recursive Comparison

#include <iostream>
using namespace std;
int calls = 0;
int fib(int n) {
	calls++;
	if (n <= 1) return n;
	return fib(n - 1) + fib(n - 2);
}
int main() {
	fib(10);
	cout << "calls: " << calls;
	return 0;
}

public class Main {
	static int calls = 0;
	static int fib(int n) {
		calls++;
		if (n <= 1) return n;
		return fib(n - 1) + fib(n - 2);
	}
	public static void main(String[] args) {
		fib(10);
		System.out.println("calls: " + calls);
	}
}

calls = 0
def fib(n):
    global calls
    calls += 1
    if n <= 1:
        return n
    return fib(n - 1) + fib(n - 2)

fib(10)
print("calls:", calls)

#include <stdio.h>
int calls = 0;
int fib(int n) {
	calls++;
	if (n <= 1) return n;
	return fib(n - 1) + fib(n - 2);
}
int main() {
	fib(10);
	printf("calls: %d", calls);
	return 0;
}

Memoization Idea

चूंकि naive recursive Fibonacci उन्हीं छोटी values को बार-बार recompute करता है, पहले से computed results (memoization) store करना उस repeated work से बचता है और running time को exponential से linear तक नीचे लाता है।

उदाहरण: Memoization Idea

#include <iostream>
#include <unordered_map>
using namespace std;
unordered_map<int, int> memo;
int fib(int n) {
	if (n <= 1) return n;
	if (memo.count(n)) return memo[n];
	return memo[n] = fib(n - 1) + fib(n - 2);
}
int main() {
	cout << fib(30);
	return 0;
}

import java.util.*;
public class Main {
	static HashMap<Integer, Integer> memo = new HashMap<>();
	static int fib(int n) {
		if (n <= 1) return n;
		if (memo.containsKey(n)) return memo.get(n);
		int result = fib(n - 1) + fib(n - 2);
		memo.put(n, result);
		return result;
	}
	public static void main(String[] args) {
		System.out.println(fib(30));
	}
}

memo = {}
def fib(n):
    if n <= 1:
        return n
    if n in memo:
        return memo[n]
    memo[n] = fib(n - 1) + fib(n - 2)
    return memo[n]

print(fib(30))

#include <stdio.h>
long memo[40] = {0};
long fib(int n) {
	if (n <= 1) return n;
	if (memo[n]) return memo[n];
	return memo[n] = fib(n - 1) + fib(n - 2);
}
int main() {
	printf("%ld", fib(30));
	return 0;
}

Practice

दोनों problems को हाथ से काम करना — factorial के लिए call stack trace करना और Fibonacci के लिए branching call tree draw करना — बाद में harder recursive और dynamic programming problems के लिए ज़रूरी intuition बनाता है।

उदाहरण: Practice

#include <iostream>
using namespace std;
int factorial(int n) { return n <= 1 ? 1 : n * factorial(n - 1); }
int fib(int n) { return n <= 1 ? n : fib(n - 1) + fib(n - 2); }
int main() {
	cout << "5! = " << factorial(5) << ", fib(6) = " << fib(6);
	return 0;
}

public class Main {
	static int factorial(int n) { return n <= 1 ? 1 : n * factorial(n - 1); }
	static int fib(int n) { return n <= 1 ? n : fib(n - 1) + fib(n - 2); }
	public static void main(String[] args) {
		System.out.println("5! = " + factorial(5) + ", fib(6) = " + fib(6));
	}
}

def factorial(n):
    return 1 if n <= 1 else n * factorial(n - 1)

def fib(n):
    return n if n <= 1 else fib(n - 1) + fib(n - 2)

print("5! =", factorial(5), ", fib(6) =", fib(6))

#include <stdio.h>
int factorial(int n) { return n <= 1 ? 1 : n * factorial(n - 1); }
int fib(int n) { return n <= 1 ? n : fib(n - 1) + fib(n - 2); }
int main() {
	printf("5! = %d, fib(6) = %d", factorial(5), fib(6));
	return 0;
}

Chapter Quiz — Complete all 7 topics to unlock

0/7 topics done

Complete these topics first:

← Previous Lesson Recursion Deep Dive Next Lesson → Tower of Hanoi