CODEWITHSUNDEEP
haskellrecursionbinary
newbie
newbie

Reputation: 1217

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

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)

Upvotes: 0

Views: 92

Answers (2)

Redu
Redu

Reputation: 26161

No need for recursion or iteration. You may perhaps do with base 2 logarithm as follows;

binaryDigits :: (Floating a, Integral c, RealFrac a) => a -> c
binaryDigits n | n == 0    = 1
               | otherwise = 1 + (floor . logBase 2 $ n)
> binaryDigits 1453
> 11

Upvotes: 0

Welperooni
Welperooni

Reputation: 643

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)

Upvotes: 4

Related Questions