Bluetooth is obvious.  You can easily put out serial data to a cheapo BT modem, and pass that off to a microcontroller.  

Pros: simple, portable, flexible, not a super power hog

Cons: slow, high latency, flexible -- need to develop own protocol

[Eric Mockler] says: I use Basic for Android and the BT for serial access.
https://www.b4x.com/b4a.html

See the bead-sorter project for another example (Droidscript + Arduino).

[MartinR] says: For making Android apps take a look at MIT App Inventor 2 http://ai2.appinventor.mit.edu Totally insane GUI programming but gives access to Bluetooth and BLE.

So many ways to go here, and a Bluetooth serial terminal is always handy...