How to properly use a function that is recursive and receives a single argument?

Question

While trying to solve the following exercise...

Define the function binaryDigits, that receives an Integer and returns the amount of digits required to write such umber in binary code.

... I found myself thinking that it is impossible to solve this problem by calling the function binaryDigits recursively because the only variable it receives is the actual number

I say this because the website states that while the tests it runs were succeeded, I didn't use recursion in the function binaryDigits.

so how could I even think of recursively call this function if I can't even tell how many times have I called it (and lets say that the number of times being called represent how many binary digits it takes to represent that number).

This is what I thought: please note that I'm using recursion but in an auxiliary function that returns a list of the decimal values that binary digits represent when the sum of that list is greater than the received number:

double = (2*)

listOfBinaryDigits list num | num > (sum list) = listOfBinaryDigits ([double(head list)]++list) num
                            | otherwise = list

binaryDigits num = length (listOfBinaryDigits [1] num)

How many digits do you need for 153? Now how many do you need for div 153 10 == 15? Or div 15 10 == 1? Or div 1 10 == 0 (hint: assume you need only 0 digits for 0 itself). — chepner

Welperooni Welperooni · Accepted Answer · 2018-06-05T19:56:04

Here's an "iterative" solution:

binaryDigits = length . takeWhile (not . (==0)) . iterate (`div` 2)

You can also redefine it by recursing until you hit the bottom and sum the length on the way back. It will be a good exercise, so I kept the solution in a spoiler for you

binaryDigits 0 = 0;
binaryDigits x = 1 + binaryDigits (div x 2)

How to properly use a function that is recursive and receives a single argument?

2 Answers