Python Q&A – Recursion

Question 1: Recursion – Extracting Digits
Recursion is a very useful way to iterate a condition over large amounts of data. In this example, it will be the simple use of recursion to extract the digits of the number inputted/analyzed.

Task: Write a recursive function getdigits(n) that returns the list of digits in the positive integer n.

Tests to Satisfy:

Answer:

Explanation: This function is relatively basic and easy to understand. The first if statement allows us to stop the recursion function if the number inputted is less than 10 (which makes sense because the number only contain a digit that is 0 – 9). The else statement allows us to reiterate over and over again if the number inputted has more than one digit. For example to satisfy the second test, the first iteration is “return getdigits(120/10) + [120%10]” which becomes “getdigits(12) + 0”. Second iteration is “return getdigits(12/10) + [12%10]” which becomes “getdigits(1) + 2”. The third iteration then stops at the if statement which return a 1. This function then exists and returns [1,2,0].

Question 2: Recursion – Nested Lists
It would be handy to have a procedure that allows accessing lists that are nested to arbitrary depth. It would take a nested list and some sort of an index, and return the part of the list at that index. The item at that index could be a primitive type such as a number or a string, or it could be another list.

Task: Write a function recursive_index(lst, index_path) which can look up a value in a nested list based on its index path. The index path will be represented as a list (eg, [1, 1, 0]). You may assume that index_path contains a valid index path for lst. 

Tests to Satisfy:

Answer:

Question 3: Recursion – Extracting Digits Using a Base
Task: Write a recursive function dec2base(n, b) that returns the list of base b digits in the positive integer n. 

Example: dec2base(120, 10) => [1,2,0] (1*10**2 + 2*10**1 + 0*10**0)

Tests to Satisfy:

Answer:

Question 4: Recursively Converting a List of Digits to a Number
Task: Write a recursive function base2dec(digits, base) that takes the list of digits in the given base and returns the corresponding base 10 number. 

Tests to Satisfy:

Answer:

, , ,

No comments yet.

Leave a Reply

Powered by WordPress. Designed by WooThemes

Free WordPress Themes