Récursivité

Objectifs
Exercices sur la récursivité

Puissance

Écrire un algorithme récursif pour le calcul de $x^n$. Dérouler l’algorithme pour $n=3$.

Suite récurrente

Soit $u_n$ définie par $u_0=1515$ et $u_{n+1}=3u_n+42$ pour $n \in N^{*}$. Écrire un algorithme récursif pour calculer $u_k$ avec $k$ donné.

Fibonacci

Soit $u_n$ définie par $u_0=1$, $u_1=1$ et $u_{n+1}=u_n+u_{n-4}$ pour $n \in N^{*}$. Écrire un algorithme récursif pour calculer $u_k$ avec $k$ donné.

Chemins sur une grille

Source: projecteuler.net #15

Starting in the top left corner of a 2×2 grid, and only being able to move to the right and down, there are exactly 6 routes to the bottom right corner.

How many such routes are there through a 20×20 grid?

Partitions de pièces

Source: projecteuler.net #78

Let p(n) represent the number of different ways in which n coins can be separated into piles. For example, five coins can separated into piles in exactly seven different ways, so p(5)=7.

OOOOO
OOOO   O
OOO   OO
OOO   O   O
OO   OO   O
OO   O   O   O
O   O   O   O   O

Find the least value of n for which p(n) is divisible by one million.