---
# System prepended metadata

title: Ch3 Recursion

---

# Ch3 Recursion

## 遞迴

是一種在演算法中常見的技巧。簡單來說，允許一個函數呼叫自己。
由兩部分組成：基本(base case)和遞迴(recursive case)。

### 基本情況：

這是函數停止遞迴的條件，在此條件後，函數不再呼叫自己。

### 遞迴情況：

在這個情況下，函數將呼叫自己。

<!-- 在第三章中，你將學習遞迴函數如何工作，以及如何用遞迴解決問題。你會看到遞迴在許多不同類型的問題中是如何應用的，包括數學問題（如計算數字的階乘）、數據結構問題（如尋找鏈表中的元素）和排序問題（如快速排序）。

這章還可能會討論一些關於遞迴的挑戰，如堆疊溢出和效率問題，以及如何通過使用迴圈或者優化遞迴深度來解決這些問題。 -->

### 範例
![](https://hackmd.io/_uploads/HkwJnePU2.png)
![](https://hackmd.io/_uploads/rJJghlDIh.png)

- 你發現了一個上鎖的盒子A
- 鑰匙可能在另外一個盒子B裡
- 盒子B裡面有盒子C，盒子C裡面又有盒子D
- 鑰匙就在某個盒子中
- 要找到鑰匙要用什麼演算法

![](https://hackmd.io/_uploads/Sy5rW64U3.png)
<!-- 翻箱倒柜 -->
![](https://hackmd.io/_uploads/rJ3S-pVU3.png)


```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![](https://hackmd.io/_uploads/rJ3GiMIUh.png)

3. 印出hello, maggie!
4. 執行greet2("maggie"), how are you, maggie!![](https://hackmd.io/_uploads/rJ3mozUUn.png)
![](https://hackmd.io/_uploads/HkqVozUL3.png)

5. 再分配一塊memory![](https://hackmd.io/_uploads/Hk7roGIU2.png)

6. 執行bye, ok bye!![](https://hackmd.io/_uploads/SJE8jf8L2.png)




使用Stack來表示這些memory使用過程, 第二塊在第一塊上面
執行4的時候, 頂部被popup
執行6添加一塊在一上面印出bye之後popup
只剩下第一塊
最後沒別的事要做，從greet返回

This is `call stack`


### Recursive call stack
![](https://hackmd.io/_uploads/ByW3agwU3.png)

```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
<!-- 翻箱倒柜 
你創建一個盒子堆 至始至終知道還有多少要尋找-->
![](https://hackmd.io/_uploads/H15FnfIL2.png)
![](https://hackmd.io/_uploads/S1atnMUL2.png)
<!-- 遞歸沒有 -->
![](https://hackmd.io/_uploads/HJE03GIL2.png)
![](https://hackmd.io/_uploads/rkOA3M8Ih.png)
![](https://hackmd.io/_uploads/HyNvyWvIn.png)

### 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.


