Recursivitat

name: portada
class: portada-slide, center, middle

# Recursivitat

.footnote[Joan Puigcerver Ibáñez]

---
layout: true
class: regular-slide
.right[.logo[![logoMislata](/itb/images/logo_mislata.png)]]

---
# Recursivitat
- Fes l'exercici N pometes

---
# Recursivitat
```pseudocode
imprimirCançoPomes(int pomes){
	if(pomes==0)
		return;
	imprimirEstrofa(pomes);
	imprimirCançoPomes(pomes-1);
}
```

---
# Recusivitat
Es diu que un codi és recursiu quan usa la recursivitat.

---
# Recursivitat
La recursivitat és la forma en la qual s'especifica un procés basat en la seva pròpia definició.
 - Les instàncies complexes d'un procés es defineixen en termes d'instàncies més simples (cas recursiu)
 - Les més simples són definides de forma explícita (cas base)

---
# Recursivatat
- Definir el cas (o casos base)
- Definir la crida recursiva

---
# Canço pomes
- Case Base
  - Si 0 pomes -> retorna ""
- Cas recursiu
  - estrofa_actual + canço_pomes(n-1)

---
# Multiplicació
multiplica(n,m)
  si m = 0
    retorna 0
  sino
    retorna n + multiplica(n,m-1)

---
# Recursivitat vs Iteració
- Alguns problemes només es poden resoldre de forma recursiva
  - MergeSort
  - SlowUpDownArray dels exercicis de classe
- Alguns problemes són més senzills de programar de forma recursiva
- Interació és més ràpida que la recursivitat
  - Casi imperceptible per la majoria de programes.

---
# Algoritmes d'ordenació
- Ordenament de bombolla ([Bubblesort](https://ca.wikipedia.org/wiki/Bubble-sort))
- [Merge sort ](https://www.geeksforgeeks.org/merge-sort/)
- [Heapsort](https://ca.wikipedia.org/wiki/Heapsort)
- [Quick Sort](https://ca.wikipedia.org/wiki/Quicksort)

---
# MergeSort