# Ch3 Recursion
## 遞迴
是一種在演算法中常見的技巧。簡單來說，允許一個函數呼叫自己。
由兩部分組成：基本(base case)和遞迴(recursive case)。
### 基本情況：
這是函數停止遞迴的條件，在此條件後，函數不再呼叫自己。
### 遞迴情況：
在這個情況下，函數將呼叫自己。
<!-- 在第三章中，你將學習遞迴函數如何工作，以及如何用遞迴解決問題。你會看到遞迴在許多不同類型的問題中是如何應用的，包括數學問題（如計算數字的階乘）、數據結構問題（如尋找鏈表中的元素）和排序問題（如快速排序）。
這章還可能會討論一些關於遞迴的挑戰，如堆疊溢出和效率問題，以及如何通過使用迴圈或者優化遞迴深度來解決這些問題。 -->
### 範例
- 你發現了一個上鎖的盒子A
- 鑰匙可能在另外一個盒子B裡
- 盒子B裡面有盒子C，盒子C裡面又有盒子D
- 鑰匙就在某個盒子中
- 要找到鑰匙要用什麼演算法
<!-- 翻箱倒柜 -->
```ruby=
# First, while loop
def look_for_key(main_box)
pile = main_box.make_a_pile_to_look_through
while !pile.empty?
box = pile.grab_a_box
box.each do |item|
if item.is_a_box?
pile.append(item)
elsif item.is_a_key?
puts "found the key!"
end
end
end
end
# Second, Recursion version
def look_for_key(box)
box.each do |item|
if item.is_a_box?
look_for_key(item)
elsif item.is_a_key?
puts "found the key!"
end
end
# end
end
```
這兩種方法的作用相同，
- Recursion方法更清晰。
- Recursion沒有性能上的優勢。
Stack Overflow:
- "Loops may achieve a performance gain for your program."
- "Recursion may achieve a performance gain for your programmer. Choose which is more important in your situation!"
### Base and Recursive case
```ruby
def fibonacci(n)
a = 0
b = 1
n.times do
temp = a
a = b
b = temp + b
end
return a
end
# 1、 1、 2、 3、 5、 8、 13、 21、 34、 55
puts fibonacci(10) # => 55
```
```ruby=
def fibonacci(n)
return n if n <= 1 # Base case
fibonacci(n - 1) + fibonacci(n - 2) # Recusive case
end
puts fibonacci(10) # => 55
```
### Stack
```ruby
def greet(name)
puts "hello, " + name + "!"
greet2(name)
puts "getting ready to say bye..."
bye()
end
def greet(name)
puts "how are you, " + name + "!"
end
def bye
puts "ok bye!"
end
```
> greet("maggie")
1. 分配一塊memory
2. name被設置為maggie
3. 印出hello, maggie!
4. 執行greet2("maggie"), how are you, maggie!
5. 再分配一塊memory
6. 執行bye, ok bye!
使用Stack來表示這些memory使用過程, 第二塊在第一塊上面
執行4的時候, 頂部被popup
執行6添加一塊在一上面印出bye之後popup
只剩下第一塊
最後沒別的事要做，從greet返回
This is `call stack`
### Recursive call stack
```ruby
def fact(n)
return 1 if n <= 1
n * fact(n - 1)
end
puts fact(3) # => 6
# 3 * 2 * 1
puts fact(5) # => 120
# 5 * 4 * 3 * 2 * 1
```
### Recap
<!-- 翻箱倒柜
你創建一個盒子堆 至始至終知道還有多少要尋找-->
<!-- 遞歸沒有 -->
### Stack很方便，但有代價
1. Take up a lof of memory
2. Refactor to loop
3. Tail recursion
- Scheme: Scheme is a functional programming language and dialect of Lisp that was designed to have good support for recursive programming patterns. It has excellent support for tail recursion.
- Haskell: Haskell is a purely functional programming language with strong support for tail recursion.
- Erlang and Elixir: These are functional programming languages built on the BEAM virtual machine, which has built-in support for tail recursion. They are often used in systems that require high concurrency, fault tolerance, and distributed processing.
- Clojure: This is a modern functional programming language that is a dialect of Lisp, and it runs on the Java virtual machine (JVM). It also has good support for tail recursion.
- Scala: Scala, another JVM language, supports tail recursion and the Scala compiler will optimize tail recursive functions. However, it requires the recursive call to be the last operation in the function.
- Rust: Rust is a systems programming language that supports tail call optimization, but only in release mode.
```ruby=
# Tail recursion in ruby
def factorial(n, acc = 1)
return acc if n <= 1
factorial(n - 1, n * acc)
end
```
### Conclusion
- Recursion is when a function calls itself.
- Every recursive function has two cases: the base case and the recursive case.
- A stack has two operations: push and pop.
- All function calls go onto the call stack.
- The call stack can get very large, which takes up a lot of memory.
Sign in with Wallet
Connect another wallet